HDU3605Escape（最大流SAP+狀態壓縮優化點的個數）

Escape

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 6239 Accepted Submission(s): 1474


Problem Description 2012 If this is the end of the world how to do? I do not know how. But now scientists have found that some stars, who can live, but some people do not fit to live some of the planet. Now scientists want your help, is to determine what all of people can live in these planets.

Input More 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

Output Determine 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

Source 2010 ACM-ICPC Multi-University Training Contest（17）——Host by ZSTU

題意：現在地球有n（<=100w）人數要去m（<=10）個其他星球生存，接下來n行每行m列，如果第i 為 1 對應這個人可去星球 i ，第 i 個星球最多可容ai個人（最後一行給出m個數）。現在問是否所有的人都可以到其他星球生存。

解題：最大流SAP。建圖：因為人數多，而去星球的狀態少最多是1024種，所以可以把每種狀態看作是點，源點與每種狀態連接一條邊，容量為當前狀態的人數，再每種狀態與相應的星球連邊，邊容為當前狀態的人數。再每個星球與匯點連邊，邊容為星球能容納的人數。

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

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

 

#include
#include
#include
#include
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]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(i0 ){
            if(k[i]>0){ //出現的狀態
                addEdg(s , id , k[i]);
                j=0;
                while( (1<0?:);
    }
}