状态压缩+最大流

首先我们可以很明显的看出这是一个最大流问题。
其实我们也是可以将这题看成一个匹配问题，用hk算法可能能过。我没有试。

我们给出最大流做法。
我们发现这里的点数实在是太多了，直接使用最大流算法肯定会超时。
那么，我们分析题目。发现，行星m最多只有10颗。
这意味着什么呢？
意味着，对于一个人她对行星的适应性最多只有2^11-1种情况！！
即2048种情况，那么我们可以一口气将点数减少很多。

#include<iostream>
#include<algorithm>
#include<vector>
#include<functional>
using namespace std;
const int max_n = 2100;
const int max_m = 1e5+100;
const int inf=0x3f3f3f3f;
struct edge {
    int to,cap,next;
}E[max_m<<2];
int n,m;
int head[max_n],cnt=1,gap[max_n],last[max_n],d[max_n],que[max_n],ql,qr;
void add(int u,int to,int cap) {
    E[++cnt].to=to;E[cnt].cap=cap;
    E[cnt].next=head[u];head[u]=cnt;
    E[++cnt].to=u;E[cnt].cap=0;
    E[cnt].next=head[to];head[to]=cnt;
}int aug(int x,int s,int t,int mi) {
    if (x==t) return mi;
    int flow=0;
    for (int &i=last[x],v=E[i].to;i;i=E[i].next,v=E[i].to) if (d[x]==d[v]+1) {
        int tmp=aug(v,s,t,min(mi,E[i].cap));
        flow+=tmp,mi-=tmp,E[i].cap-=tmp,E[i^1].cap+=tmp;
        if (!mi) return flow;
    }
    if (!(--gap[d[x]])) d[s]=n+1;
    ++gap[++d[x]],last[x]=head[x];
    return flow;
}
int maxflow(int s,int t) {
    fill(gap,gap+n+10,0);fill(d,d+n+10,0);
    ++gap[d[t]=1];
    for (int i=1;i<=n;++i) last[i]=head[i];
    que[ql=qr=1]=t;
    while (ql<=qr) {
        int x=que[ql++];
        for (int i=head[x],v=E[i].to;i;i=E[i].next,v=E[i].to) if (!d[v]) ++gap[d[v]=d[x]+1],que[++qr]=v;
    }

    int ret=aug(s,s,t,inf);
    while (d[s]<=n)    ret+=aug(s,s,t,inf);
    return ret;
}
int cct[2100];
int main(){
    while (~scanf("%d %d",&n,&m)){
        fill(head,head+2100,0);cnt=1;
        fill(cct,cct+2100,0);
        for (int i=1;i<=n;++i){
            int node = 0;
            for (int j=0;j<m;++j){
                int val;scanf("%d",&val);
                if (val==1)node|=(1<<j);
            }
            ++cct[node];
        }

        int s = 2080;int ed = s+1;
        for (int i=0;i<m;++i){
            int cap;scanf("%d",&cap);
            add(i+2050,ed,cap);
        }

        for (int node=1;node<2049;++node){
            if (cct[node]==0)continue;
            add(s,node,cct[node]);
            for (int i=0;i<m;++i)
                if ((node>>i)&1)
                    add(node,2050+i,cct[node]);
        }
        int tn = n;
        n = 2100;
        if (tn==maxflow(s,ed))printf("YES\n");
        else printf("NO\n");
    }
}