HDU 3605 Escape （最大流 或 Hungary）

Escape

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

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

 

 

Recommend

lcy

 

 

 

发现可以合并点，

因为m<=10.

所以用二进制记录。

在n个点中，如果是一样的就合并。

这样最多是1024+m+2个点。

 

 

但是这题还是很坑。。。。在HDU上用G++交无论如何都是TLE的。直接读入数据输出都是TLE.

改成C++就AC了。。

 

1，最大流：

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>

using namespace std;

const int VM=101000;
const int EM=500010;
const int INF=0x3f3f3f3f;

int n,m,cnt,head[VM];
int dep[VM],gap[VM],cur[VM],aug[VM],pre[VM];
    //dep表示每个点的距离标记，gap表示距离为i的点有多少个，cur用于当前孤优化，
    //aug记录找到的增广路流量，path记录找到的增广路的路径。

struct Edge{
    int u,v,nxt;
    int cap;
}edge[EM];

void addedge(int cu,int cv,int cw){
    edge[cnt].u=cu;  edge[cnt].v=cv;  edge[cnt].cap=cw;
    edge[cnt].nxt=head[cu];  head[cu]=cnt++;
    edge[cnt].u=cv;  edge[cnt].v=cu;  edge[cnt].cap=0;
    edge[cnt].nxt=head[cv];  head[cv]=cnt++;
}

int src,des;

int SAP(int n){
    int max_flow=0,u=src,v;
    int id,mindep;
    aug[src]=INF;
    pre[src]=-1;
    memset(dep,0,sizeof(dep));
    memset(gap,0,sizeof(gap));
    gap[0]=n;
    for(int i=0;i<=n;i++)
        cur[i]=head[i]; // 初始化当前弧为第一条弧
    while(dep[src]<n){
        int flag=0;
        if(u==des){
            max_flow+=aug[des];
            for(v=pre[des];v!=-1;v=pre[v]){     // 路径回溯更新残留网络
                id=cur[v];
                edge[id].cap-=aug[des];
                edge[id^1].cap+=aug[des];
                aug[v]-=aug[des];   // 修改可增广量，以后会用到
                if(edge[id].cap==0) // 不回退到源点，仅回退到容量为0的弧的弧尾
                    u=v;
            }
        }
        for(int i=cur[u];i!=-1;i=edge[i].nxt){
            v=edge[i].v;    // 从当前弧开始查找允许弧
            if(edge[i].cap>0 && dep[u]==dep[v]+1){  // 找到允许弧
                flag=1;
                pre[v]=u;
                cur[u]=i;
                aug[v]=min(aug[u],edge[i].cap);
                u=v;
                break;
            }
        }
        if(!flag){
            if(--gap[dep[u]]==0)    /* gap优化，层次树出现断层则结束算法 */
                break;
            mindep=n;
            cur[u]=head[u];
            for(int i=head[u];i!=-1;i=edge[i].nxt){
                v=edge[i].v;
                if(edge[i].cap>0 && dep[v]<mindep){
                    mindep=dep[v];
                    cur[u]=i;   // 修改标号的同时修改当前弧
                }
            }
            dep[u]=mindep+1;
            gap[dep[u]]++;
            if(u!=src)  // 回溯继续寻找允许弧
                u=pre[u];
        }
    }
    return max_flow;
}

int main(){

    //freopen("input.txt","r",stdin);

    int num[1025],a[12],bit[12];
    bit[0]=1;
    for(int i=1;i<=10;i++)
        bit[i]=bit[i-1]<<1;
    while(~scanf("%d%d",&n,&m)){
        cnt=0;
        memset(head,-1,sizeof(head));
        memset(num,0,sizeof(num));
        for(int i=1;i<=n;i++){  //缩点
            int tmp=0;
            for(int j=0;j<m;j++){
                scanf("%d",&a[j]);
                tmp+=a[j]*bit[j];
            }
            num[tmp]++;
        }
        src=0,des=1024+m+1;
        int nodenum=1024+m+2;
        for(int i=0;i<1024;i++){
            if(num[i]==0)
                continue;
            addedge(src,i+1,num[i]);
            for(int j=0;j<10;j++)
                if(i&bit[j])
                    addedge(i+1,1024+j+1,INF);
        }
        int tmp;
        for(int i=1;i<=m;i++){
            scanf("%d",&tmp);
            addedge(i+1024,des,tmp);
        }
        if(SAP(nodenum)==n)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

 

 

2，Hungary

 

 

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

const int N=100010;
const int M=12;

int map[N][M],cap[M],num[M];    //i适合在j上生存  ,  星球的容量,,星球上人数  
int linker[N][M],vis[M];
int n,m,flag;

int in()
{
    char ch;
    int a = 0;
    while((ch = getchar()) == ' ' || ch == '\n');
    a += ch - '0';
    while((ch = getchar()) != ' ' && ch != '\n')
    {
        a *= 10;
        a += ch - '0';
    }
    return a;
}

int DFS(int u){
    int v;
    for(v=0;v<m;v++)    //枚举每个星球
        if(!vis[v] && map[u][v]){
            vis[v]=1;
            if(num[v]<cap[v]){  //i星球上人数小于容量 
                linker[num[v]++][v]=u;
                return 1;
            }
            for(int j=0;j<num[v];j++)
                if(DFS(linker[j][v])){  //给link[i][j]找新的星球
                    linker[j][v]=u;
                    return 1;
                }
        }
    return 0;
}

void Hungary(){
    //memset(linker,-1,sizeof(linker));
    for(int u=0;u<n;u++){
        memset(vis,0,sizeof(vis));
        if(!DFS(u)){
            flag=0;
            break;
        }
    }
}

int main(){

    //freopen("input.txt","r",stdin);

    while(~scanf("%d%d",&n,&m)){
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                map[i][j]=in(); //此题用scanf则TLE，，哎，只能自己写输入函数了
        for(int i=0;i<m;i++)
            scanf("%d",&cap[i]);
        memset(num,0,sizeof(num));
        flag=1;
        Hungary();
        if(flag)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}