InputMore 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
OutputDetermine 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 题目大意：就是星球移民，不同的人对不同的星球适应情况不同，给你m个人n个星球和每个人对星球的适应情况，和每一个星球最大承载人数，让你求是否可以全部成功移民。
这个题目是一个比较明显的网络流，但是dinic的复杂度是n*n*m，所以这个直接跑网络流肯定会超时。
然后我就T了，虽然知道自己超时了，不过并没有想到怎么解决。
然后搜题解，就看到了状态压缩。
就是因为m=10，所以可以去考虑可能有些人对星球的适应情况是一样的，这个要用二进制的方式去转化
怎么个状态压缩呢？
就是因为可能有些人对星球的适应情况完全相同，所以就把人对星球的适应状况压缩成只含有01的数字。
然后用map存储，这个之后就是建图了，
建图你只要知道，你只需要利用map的数据建图就可以了，建好图map数组就没什么用了，所以你不需要一个对应关系。
这个建图就看代码吧。
这个卡cin
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <iostream>
#include <vector>
#include <map>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn = 1e5 + ;
typedef long long ll;
int s, t, n, m;
struct node
{
int from, to, cap, flow;
node(int from=,int to=,int cap=,int flow=):from(from),to(to),cap(cap),flow(flow){}
};
vector<node>e;
vector<int>G[maxn];
void add(int u,int v,int c)
{
e.push_back(node(u, v, c, ));
e.push_back(node(v, u, , ));
int m = e.size();
G[u].push_back(m - );
G[v].push_back(m - );
}
int level[maxn], iter[maxn];
void bfs(int s)
{
queue<int>que;
que.push(s);
memset(level, -, sizeof(level));
level[s] = ;
while(!que.empty())
{
int u = que.front(); que.pop();
for(int i=;i<G[u].size();i++)
{
node &now = e[G[u][i]];
if(now.cap>now.flow&&level[now.to]<)
{
level[now.to] = level[u] + ;
que.push(now.to);
}
}
}
} int dfs(int u,int v,int f)
{
if (u == v) return f;
for(int &i=iter[u];i<G[u].size();i++)
{
node &now = e[G[u][i]];
if(now.cap>now.flow&&level[now.to]>level[u])
{
int d = dfs(now.to, v, min(f, now.cap - now.flow));
if(d>)
{
now.flow += d;
e[G[u][i] ^ ].flow -= d;
return d;
}
}
}
return ;
}
map<int, int>mp;
int dinic()
{
int flow = ;
while()
{
bfs(s);
if (level[t] < ) return flow;
for (int i = s; i <= t; i++) iter[i] = ;
int f;
while ((f = dfs(s, t, inf)) > ) flow += f;
}
} void init()
{
for (int i = ; i <= n+m+; i++) G[i].clear();
e.clear();
mp.clear();
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
init();
s = ;
for(int i=;i<=n;i++)
{
int ret = ;
for(int j=;j<=m;j++)
{
int x; scanf("%d", &x);
ret = ret + (x << j);
}
mp[ret]++;
}
int cnt = mp.size();
int num = ;
map<int, int>::iterator p;
for(p=mp.begin();p!=mp.end(); p++)
{
num++;
for(int i=;i<=m;i++)
{
if ((p->first)&( << i))
{
add(num, cnt + i, p->second);
}
}
add(s, num, p->second);
}
t = num + m + ;
for(int i=;i<=m;i++)
{
int x; scanf("%d", &x);
add(num + i, t, x);
}
int ans = dinic();
if (ans >= n) printf("YES\n");
else printf("NO\n");
}
return ;
}