Escape

1 1
1
1

2 2
1 0
1 0
1 1

YES
NO

题意：现在地球有n（<=100w）人数要去m（<=10）个其他星球生存，接下来n行每行m列，如果第i 为 1 对应这个人可去星球 i ，第 i 个星球最多可容ai个人（最后一行给出m个数）。现在问是否所有的人都可以到其他星球生存。

解题：最大流SAP。建图：因为人数多，而去星球的状态少最多是1024种，所以可以把每种状态看作是点，源点与每种状态连接一条边，容量为当前状态的人数，再每种状态与相应的星球连边，边容为当前状态的人数。再每个星球与汇点连边，边容为星球能容纳的人数。

另一种方法解：多重匹配，人作x部分和星球作y部分，形成二部图。

下面是最大流SAP解法：用G++  。

#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std;
#define captype int

const int MAXN = 1030;   //点的总数
const int MAXM = 14000;    //边的总数
const int INF = 1<<30;

struct EDG{
    int to,next;
    captype cap,flow;
} edg[MAXM];
int eid,head[MAXN];
int gap[MAXN];  //每种距离(或可认为是高度)点的个数
int dis[MAXN];  //每个点到终点eNode 的最短距离
int cur[MAXN];  //cur[u] 表示从u点出发可流经 cur[u] 号边
int pre[MAXN];

inline void init(){
    eid=0;
    memset(head,-1,sizeof(head));
}
//有向边 三个参数，无向边4个参数
inline void addEdg(int u,int v,captype c,captype rc=0){
    edg[eid].to=v; edg[eid].next=head[u];
    edg[eid].cap=c; edg[eid].flow=0; head[u]=eid++;

    edg[eid].to=u; edg[eid].next=head[v];
    edg[eid].cap=rc; edg[eid].flow=0; head[v]=eid++;
}
inline captype maxFlow_sap(int& sNode,int& eNode, int n){//n是包括源点和汇点的总点个数，这个一定要注意
    memset(gap,0,sizeof(gap));
    memset(dis,0,sizeof(dis));
    memcpy(cur,head,sizeof(head));
    pre[sNode] = -1;
    gap[0]=n;
    captype ans=0;  //最大流
    int u=sNode  , i ;
    while(dis[sNode]<n){   //判断从sNode点有没有流向下一个相邻的点
        if(u==eNode){   //找到一条可增流的路
            captype Min=INF ;
            int inser ;
            i=pre[u] ;
            while( i!=-1 ){    //从这条可增流的路找到最多可增的流量Min
                if(Min>edg[i].cap-edg[i].flow){
                    Min=edg[i].cap-edg[i].flow;
                    inser=i;
                }
                i=pre[edg[i^1].to];
            }

            i=pre[u];
            while( i!=-1 ){
                edg[i].flow+=Min;
                edg[i^1].flow-=Min;  //可回流的边的流量
                i=pre[edg[i^1].to];
            }
            ans+=Min;
            u=edg[inser^1].to;
            continue;
        }
        bool flag = false;  //判断能否从u点出发可往相邻点流
        int v;
        i=cur[u];
        while(  i!=-1 ){
            v=edg[i].to;
            if(edg[i].cap-edg[i].flow>0 && dis[u]==dis[v]+1){
                flag=true;
                cur[u]=pre[v]=i;
                break;
            }
            i=edg[i].next;
        }
        if(flag){
            u=v;
            continue;
        }
        //如果上面没有找到一个可流的相邻点，则改变出发点u的距离（也可认为是高度）为相邻可流点的最小距离+1
        int Mind= n;
        i=head[u];
        while(  i!=-1 ){
             if(edg[i].cap-edg[i].flow>0 && Mind>dis[edg[i].to]){
                 Mind=dis[edg[i].to];
                 cur[u]=i;
             }
            i=edg[i].next;
        }

        gap[dis[u]]--;
        if(gap[dis[u]]==0) return ans;  //当dis[u]这种距离的点没有了，也就不可能从源点出发找到一条增广流路径
                                        //因为汇点到当前点的距离只有一种，那么从源点到汇点必然经过当前点，然而当前点又没能找到可流向的点，那么必然断流
        dis[u]=Mind+1;//如果找到一个可流的相邻点，则距离为相邻点距离+1，如果找不到，则为n+1
        gap[dis[u]]++;
        if(u!=sNode) u=edg[pre[u]^1].to;  //退一条边
    }
    return ans;
}
inline void scanf(int& valu){
    char ch;
    while(ch=getchar()){
        if(ch>='0'&&ch<='9')
            break;
    }
    valu=ch-'0';
    while(ch=getchar()){
        if(ch<'0' || ch>'9')
            break;
        valu=valu*10+ch-'0';
    }
}

int main(){
    int n,m,a , s ,t ,ans ,k[1030] ;
    while(scanf("%d%d",&n,&m)>0){
        memset(k,0,sizeof(k));
        int id=0 , i=0 ,j;
        while(i<n){
            int b=0;
            j=0;
            while( j<m ){
                scanf(a);   if(a) b|=1<<j; j++;
            }
            if(k[b]==0&&b) //出现状态的不同个数e
                id++;
            k[b]++;
            i++;
        }
        ans=n;
        init();

        n=id;
        s=0; t= n+m+1;
        i=(1<<m)-1;
        while(i>0 ){
            if(k[i]>0){ //出现的状态
                addEdg(s , id , k[i]);
                j=0;
                while( (1<<j)<=i ){
                    if(i&(1<<j)) addEdg( id , j+n+1 , k[i]); j++;
                }
                id--;
            }
            i--;
        }
        j=0;
        while( j<m ){
            scanf(a);   if(a) addEdg(j+n+1 , t , a);  j++;
        }
        ans-=maxFlow_sap(s , t, t+1);
        if(ans)
            puts("NO");
        else
            puts("YES");
       // printf("%s\n",ans>0?:);
    }
}

HDU3605Escape（最大流SAP+状态压缩优化点的个数）

原文：http://blog.csdn.net/u010372095/article/details/46494039