Escape

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 14541 Accepted Submission(s): 3666

Problem Description
2012 If this is the end of the world how to do? I do not know how. But now scientists have found that some stars, who can live, but some people do not fit to live some of the planet. Now scientists want your help, is to determine what all of people can live in these planets.

Input
More set of test data, the beginning of each data is n (1 <= n <= 100000), m (1 <= m <= 10) n indicate there n people on the earth, m representatives m planet, planet and people labels are from 0. Here are n lines, each line represents a suitable living conditions of people, each row has m digits, the ith digits is 1, said that a person is fit to live in the ith-planet, or is 0 for this person is not suitable for living in the ith planet.
The last line has m digits, the ith digit ai indicates the ith planet can contain ai people most…
0 <= ai <= 100000

Output
Determine whether all people can live up to these stars
If you can output YES, otherwise output NO.

Sample Input
1 1
1
1

2 2
1 0
1 0
1 1

Sample Output
YES
NO

先看到这道题的时候（这不就是拆点限流，跑一跑最大流再比较不就完了吗？）在一看数据，，诶，好像有点大，优化一下说不定能过，然后就各种当前弧优化，炸点优化，流量剪枝优化。。。。。。不过还是TLE到飞起。。。。。。。。。。。。。。。。。。

正解：对不同的人进行状态压缩。

怎么状态压缩呢？对于数据我们可以看到最多10个星球，而每个人对于星球要么可以去，要么不能去，所以我们想象一下，对于不同的人，用十位的二进制表示，那么也就1024种的人，然后再跑最大流即可。

比如这四个点：
00表示哪个星球都不适合这种人。
01表示后边那个星球适合这种人。
10表示前边哪个星球适合这种人。
11表示前边后边两个星球都适合这种人。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,M=4e6+10;
int n,m,s,t,h[N],vis[1200];
int head[N],nex[M],w[M],to[M],tot=1;
inline void ade(int a,int b,int c){
	to[++tot]=b; w[tot]=c; nex[tot]=head[a]; head[a]=tot;
}
inline void add(int a,int b,int c){
	ade(a,b,c);	ade(b,a,0);
}
int bfs(){
	memset(h,0,sizeof h);	h[s]=1;	queue<int> q;	q.push(s);
	while(q.size()){
		int u=q.front();	q.pop();
		for(int i=head[u];i;i=nex[i]){
			if(w[i]&&!h[to[i]]){
				h[to[i]]=h[u]+1;	q.push(to[i]);
			}
		}
	}
	return h[t];
}
int dfs(int x,int f){
	if(x==t)	return f;
	int fl=0;
	for(int i=head[x];i&&f;i=nex[i]){
		if(w[i]&&h[to[i]]==h[x]+1){
			int mi=dfs(to[i],min(w[i],f));
			w[i]-=mi;	w[i^1]+=mi;	fl+=mi;	f-=mi;
		}
	}
	if(!fl)	h[x]=-1;
	return fl;
}
int dinic(){
	int res=0;
	while(bfs())	res+=dfs(s,0x3f3f3f3f);
	return res;
}
signed main(){
	while(~scanf("%d %d",&n,&m)){
		memset(head,0,sizeof head);	tot=1;	s=m*2+3999;	t=m*2+4000;
		memset(vis,0,sizeof vis);
		for(int i=1;i<=n;i++){
			int base=0;
			for(int j=1;j<=m;j++){
				int x;	scanf("%d",&x);	if(x)	base+=1<<(j-1);
			}
			vis[base]++;
		}
		for(int i=0;i<1024;i++){
			if(!vis[i])	continue;
			add(s,i,vis[i]);
			for(int j=1;j<=10;j++){
				if(i&(1<<(j-1)))	add(i,j+2000,vis[i]);
			}
		}
		for(int i=1;i<=m;i++){
			int x;	scanf("%d",&x);	add(2000+i,2000+m+i,x);	add(2000+m+i,t,x);
		}
		if(dinic()==n)	puts("YES");
		else	puts("NO");
	}
	return 0;
}