二分图判定

没啥技巧，最难的是把图论模型建起来。

luogu1330 封锁阳光大学

相邻两个点只能封锁一个，但是要覆盖所有边。对应到二分图上就是左部右部点的数量取较小值。

图可能不连通，取的是每一张二分图的左右边的较小值。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
const int N=1e4+5;
int n, m, c[N], deg[N];
vector<int> p[N];
int c1, c2;
void add(int x,int y) {
	p[x].pb(y), p[y].pb(x);
}
bool dfs(int x,int col) {
	c[x]=col;
	if(col==1) ++c1; else ++c2;
	bool res=1;
	for(auto y:p[x]) {
		if(!c[y]) res&=dfs(y,3-col);
		else res&=(c[y]!=col);
	}
	return res;
}
signed main() {
	n=read(), m=read();
	rep(i,1,m) {
		int x=read(), y=read();
		++deg[x], ++deg[y];
		add(x,y);
	}
	int ans=0;
	rep(i,1,n) if(!c[i]) {
		c1=c2=0;
		if(!dfs(i,1)) { puts("Impossible"); return 0; }
		ans+=min(c1,c2);
	}
	printf("%lld\n",ans);
	return 0;
}

luogu1155 [NOIP2008 提高组] 双栈排序

考虑什么情况下，两个元素不能在用一个栈中。注意不一定是同时，先后进栈也算。

不难发现 \(i,j\) 不能在同一个栈中，当且仅当存在 \((i,j,k)\)，满足 \(i<j<k\)，\(a_k <a_i < a_j\)。

考虑在 \(i,j\) 之间连边，表示二者不能用同一个栈，那么有解当且仅当这张图是二分图。

考虑如何构造方案。

对图黑白染色，编号小的点贪心染白色，同时规定第一个栈是白色栈。

维护一个全局变量 \(now\) 表示下一个应该放哪个元素，从 \(1\) 到 \(n\) 扫一遍，对于一个将要加入的 \(a_i\)，维护它所在颜色的栈中元素单调递增，同时判断栈顶是否是 \(now\)，如果不是就输出另一个栈的栈顶。

由于白色栈的操作优先级都要高于黑色栈，所以在加入 \(a_i\) 之前，应该输出白栈的栈顶直到不是 \(now\)。

最后输出剩下的元素，贪心白色栈即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
const int N=1005;
int n, now=1, a[N], suf[N], c[N];
vector<int> p[N];
void add(int x,int y) {
	p[x].pb(y), p[y].pb(x);
}
bool dfs(int x,int col) {
	c[x]=col;
	bool res=1;
	for(auto y:p[x]) {
		if(!c[y]) res&=dfs(y,3-col);
		else res&=(c[y]!=col);
		if(!res) return 0;
	}
	return 1;
}
stack<int> s[3];
bool check(int col) {
	return s[col].size()&&s[col].top()==now;
}
void out(int col) {
	s[col].pop();
	++now;
	if(col==1) printf("b ");
	else printf("d ");
}
signed main() {
	n=read();
	rep(i,1,n) a[i]=read();
	suf[n]=a[n];
	per(i,n-1,1) suf[i]=min(suf[i+1],a[i]);
	rep(i,1,n) rep(j,i+1,n-1) {
		if(suf[j+1]<a[i]&&a[i]<a[j]) add(i,j);
	}
	rep(i,1,n) if(!c[i]) {
		if(!dfs(i,1)) { puts("0"); return 0; }
	}
	rep(i,1,n) {
		while(s[c[i]].size()&&s[c[i]].top()<=a[i]) {
			if(check(c[i])) out(c[i]);
			else out(3-c[i]);
		}
		while(check(1)) out(1);
		s[c[i]].push(a[i]);
		if(c[i]==1) printf("a "); else printf("c ");
	}
	while(s[1].size()||s[2].size()) {
		if(check(1)) out(1);
		else if(check(2)) out(2);
	}
	return 0;
}

luogu1285 队员分组

老题，从其他 OJ 扒来的换皮题，但是质量意外的高啊。

预处理出所有不互相认识的人，他们一定不能在同一组。在他们之间连边，发现如果有解当且仅当连出的图是二分图。

题目要求最小化两组人数之差，但是多个连通块一起考虑显然很难做。这时候可以利用连通块之间相对独立的性质，对每个连通块单独考虑，同时只有单独一个连通块的分组方法是确定的。

这时候我们能发现，每个连通块有两种颜色，每个颜色的所有点都必须一起选择，但是不同连通块的不同颜色却可以分到同一组。因此问题转化为分组背包。

设 \(f(i,j)\) 为考虑前 \(i\) 个连通块，能否选择 \(j\) 个点。转移是平凡的，同时记录到达 \(f(i,j)\) 的最后一个决策是选择的哪个颜色。

设连通块个数为 \(m\)。

分成两组，必然有一组人数不超过 \(n / 2\)。找到 \(f(m,i)\) 中满足 \(j \le n/2\) 且 \(f(n,j)=1\) 的极大的 \(j\)，这就是人数较少那组的人数了。

此时我们就可以利用记录的决策输出方案了。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
const int N=105;
int n, a[N][N], col[N];
int cnt;
vector<int> p[N], con[N][2], ans[2];
int f[N][N], op[N][N];
void add(int x,int y) {
	p[x].pb(y), p[y].pb(x);
}
void input() {
	n=read();
	rep(i,1,n) {
		int j;
		do {
			j=read();
			a[i][j]=1;
		} while(j);
	}
}
void build() {
	rep(i,1,n) rep(j,1,n) if(i!=j) {
		if(!a[i][j]||!a[j][i]) add(i,j);
	}
}
bool dfs(int x,int color) {
	col[x]=color;
	con[cnt][col[x]].pb(x);
	int res=1;
	for(auto y:p[x]) {
		if(~col[y]) res&=(col[y]!=col[x]);
		else res&=dfs(y,col[x]^1);
		if(!res) return 0;
	}
	return 1;
}
void getcol() {
	SET(col,-1);
	rep(i,1,n) if(col[i]<0) {
		++cnt;
		if(!dfs(i,0)) { puts("No solution"); exit(0); }
	}
}
#define sz(x) con[i][x].size()
void getans(int i,int j) {
	if(i<1) return;
	for(auto x:con[i][op[i][j]]) ans[0].pb(x);
	for(auto x:con[i][op[i][j]^1]) ans[1].pb(x);
	getans(i-1,j-sz(op[i][j]));
}
void dp() {
	
	f[0][0]=1;
	rep(i,1,cnt) rep(j,0,n) {
		if(j>=sz(0)&&f[i-1][j-sz(0)]) f[i][j]=1, op[i][j]=0;
		if(j>=sz(1)&&f[i-1][j-sz(1)]) f[i][j]=1, op[i][j]=1;
        // 都可以的话0/1随便取一个
	}
	int j=0;
	for(int i=n/2;i;--i) if(f[cnt][i]) { j=i; break; }
	getans(cnt,j);
	
}
void output() {
	sort(ans[0].begin(),ans[0].end());
	sort(ans[1].begin(),ans[1].end());
    // 注意输出要排序
	printf("%lld ",(int)ans[0].size());
	for(auto x:ans[0]) printf("%lld ",x);
	puts("");
	printf("%lld ",(int)ans[1].size());
	for(auto x:ans[1]) printf("%lld ",x);
}
signed main() {
	input();
	build();
	getcol();
	dp();
	output();
	return 0;
}