HDU 3605 Escape

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cmath>
  5 #include <algorithm>
  6 #include <climits>
  7 #include <vector>
  8 #include <queue>
  9 #include <cstdlib>
 10 #include <string>
 11 #include <set>
 12 #include <stack>
 13 #define LL long long
 14 #define pii pair<int,int>
 15 #define INF 0x3f3f3f3f
 16 using namespace std;
 17 const int maxn = 200010;
 18 struct arc{
 19     int to,flow,next;
 20     arc(int x = 0,int y = 0,int z = -1){
 21         to = x;
 22         flow = y;
 23         next = z;
 24     }
 25 };
 26 arc e[1000000];
 27 int head[maxn],d[maxn],cur[maxn];
 28 int tot,s,t,n,m;
 29 void add(int u,int v,int flow){
 30     e[tot] = arc(v,flow,head[u]);
 31     head[u] = tot++;
 32     e[tot] = arc(u,0,head[v]);
 33     head[v] = tot++;
 34 }
 35 int q[1000000],hd,tl;
 36 bool bfs(){
 37     //queue<int>q;
 38     hd = tl = 0;
 39     memset(d,-1,sizeof(d));
 40     d[s] = 1;
 41     //q.push(s);
 42     q[tl++] = s;
 43     while(hd < tl){
 44         int u = q[hd++];
 45         //q.pop();
 46         for(int i = head[u]; ~i; i = e[i].next){
 47             if(e[i].flow && d[e[i].to] == -1){
 48                 d[e[i].to] = d[u] + 1;
 49                 //q.push(e[i].to);
 50                 q[tl++] = e[i].to;
 51             }
 52         }
 53     }
 54     return d[t] > -1;
 55 }
 56 int dfs(int u,int low){
 57     if(u == t) return low;
 58     int tmp = 0,a;
 59     for(int &i = cur[u]; ~i; i = e[i].next){
 60         if(e[i].flow && d[e[i].to] == d[u] + 1 && (a = dfs(e[i].to,min(low,e[i].flow)))){
 61             e[i].flow -= a;
 62             e[i^1].flow += a;
 63             tmp += a;
 64             low -= a;
 65             if(!low) break;
 66         }
 67     }
 68     if(!tmp) d[u] = -1;
 69     return tmp;
 70 }
 71 int main() {
 72     int tmp,b[1<<12];
 73     while(~scanf("%d %d",&n,&m)){
 74         memset(head,-1,sizeof(head));
 75         memset(b,0,sizeof(b));
 76         for(int i = 0; i < n; ++i){
 77             int p = 0;
 78             for(int j = 0; j < m; ++j){
 79                 scanf("%d",&tmp);
 80                 p = p<<1|(tmp&1);
 81             }
 82             b[p]++;
 83         }
 84         s = (1<<m) + m;
 85         t = (1<<m) + m + 1;
 86         for(int i = tot = 0; i < (1<<m); ++i){
 87             if(b[i]){
 88                 add(s,i,b[i]);
 89                 for(int j = 0; j < m; ++j){
 90                     if(i&(1<<j)){
 91                         add(i,(1<<m)+j,b[i]);
 92                     }
 93                 }
 94             }
 95         }
 96         for(int i = 0; i < m; ++i){
 97             scanf("%d",&tmp);
 98             add((1<<m)+i,t,tmp);
 99         }
100         int maxcap = 0;
101         while(bfs()){
102             memcpy(cur,head,sizeof(head));
103             maxcap += dfs(s,INF);
104         }
105         printf("%s\n",maxcap == n?"YES":"NO");
106     }
107     return 0;
108 }