Escape

//这题的n是1e5，直接建图最大流不论是时间还是内存都不行。因为最多只有10个星球所以当n很大时这n个人中//必然会有人能去的星球的种类是一样的，这样就可以把每人归为一类，最多(1<<10)-1种人，这样压缩一下最运行最大流//看最大流是否等于n。源点连向(1<<m)-1类容量为这一类的人的数量，(1<<m)-1类连向m个星球容量为这一类的人的数量//m个星球连向汇点容量为星球能够容纳的人数。#include<iostream>#include<cstdio>#include<cstring>#include<vector>#include<queue>using namespace std;const int maxn=2100;const int inf=0x7fffffff;int mp[maxn];struct Edge{    int from,to,cap,flow;    Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){}};struct Dinic{    int n,m,s,t;    vector<Edge>edges;    vector<int>g[maxn];    bool vis[maxn];    int d[maxn];    int cur[maxn];    void init(int n){        this->n=n;        for(int i=0;i<n;i++) g[i].clear();        edges.clear();    }    void Addedge(int from,int to,int cap){        edges.push_back(Edge(from,to,cap,0));        edges.push_back(Edge(to,from,0,0));//反向弧        m=edges.size();        g[from].push_back(m-2);        g[to].push_back(m-1);    }    bool Bfs(){        memset(vis,0,sizeof(vis));        queue<int>q;        q.push(s);        d[s]=0;        vis[s]=1;        while(!q.empty()){            int x=q.front();q.pop();            for(int i=0;i<(int)g[x].size();i++){                Edge &e=edges[g[x][i]];                if(!vis[e.to]&&e.cap>e.flow){                    vis[e.to]=1;                    d[e.to]=d[x]+1;                    q.push(e.to);                }            }        }        return vis[t];    }    int Dfs(int x,int a){        if(x==t||a==0) return a;        int flow=0,f;        for(int&i=cur[x];i<(int)g[x].size();i++){            Edge &e=edges[g[x][i]];            if(d[x]+1==d[e.to]&&(f=Dfs(e.to,min(a,e.cap-e.flow)))>0){                e.flow+=f;                edges[g[x][i]^1].flow-=f;                flow+=f;                a-=f;                if(a==0) break;            }        }        return flow;    }    int Maxflow(int s,int t){        this->s=s;this->t=t;        int flow=0;        while(Bfs()){            memset(cur,0,sizeof(cur));            flow+=Dfs(s,inf);        }        return flow;    }}dc;int main(){    int n,m;    while(scanf("%d%d",&n,&m)==2){        int M=(1<<m)-1;        dc.init(M+m+2);        int x;        memset(mp,0,sizeof(mp));        for(int i=1;i<=n;i++){            int sta=0;            for(int j=0;j<m;j++){                scanf("%d",&x);                sta|=(x<<j);            }            mp[sta]++;        }        for(int i=1;i<=M;i++){            dc.Addedge(0,i,mp[i]);            for(int j=0;j<m;j++){                if(i&(1<<j)) dc.Addedge(i,j+1+M,mp[i]);            }        }        for(int i=1;i<=m;i++){            scanf("%d",&x);            dc.Addedge(M+i,M+m+1,x);        }        if(n==dc.Maxflow(0,M+m+1)) printf("YES\n");        else printf("NO\n");    }    return 0;}