HDU - 3605 Escape (缩点+最大流/二分图多重匹配)

题意：有N(1<=N<=1e5)个人要移民到M（1<=M<=10）个星球上，每个人有自己想去的星球，每个星球有最大承载人数。问这N个人能否移民成功。

分析：可以用最大流的思路求解该问题，新建源点和汇点，源点与人间加入弧，流量为他想去的星球之和；星球和汇点间加入弧，流量为其承载数量；人和星球间加入弧，流量无限。但是本题中N很大，M却很小，所以想去星球的编号组成的二进制数最多不超过1024，那么可以将N个人缩点。然后跑最大流，满流为N。

#include<iostream>

#include<stdio.h>

#include<cmath>

#include<cstring>

#include<algorithm>

#include<vector>

#include<queue>

using namespace std;

const int MAXN =1e4+,maxm =1e6+;

const int INF=0x3f3f3f3f;

struct ISAP{

    int head[MAXN], nv, n, tot;         //nv：编号修改的上限

    int num[MAXN], d[MAXN], pre[MAXN], cur[MAXN], q[MAXN];

    struct node{

        int v, next, cap;

    }edge[maxm];

    void init(){

        memset(head,-,sizeof(head));

        tot=;

    }

    void AddEdge(int u, int v, int cap){

        edge[tot].v=v;edge[tot].cap=cap;edge[tot].next=head[u];

        head[u]=tot++;

        edge[tot].v=u;edge[tot].cap=;edge[tot].next=head[v];

        head[v]=tot++;

    }

    void bfs(int s,int t){

        memset(num,,sizeof(num));

        memset(d,-,sizeof(d));

        int f1=, f2=, i;

        q[f1++]=t;

        d[t]=;

        num[]=;

        while(f1>=f2){

            int u=q[f2++];

            for(i=head[u];i!=-;i=edge[i].next){

                int v=edge[i].v;

                if(d[v]==-){

                    d[v]=d[u]+;

                    num[d[v]]++;

                    q[f1++]=v;

                }

            }

        }

    }

    int isap(int s,int t){

        memcpy(cur,head,sizeof(cur));

        int flow=, i, u=pre[s]=s;

        bfs(s,t);

        while(d[s]<nv){

            if(u==t){

                int f=INF, pos;

                for(i=s;i!=t;i=edge[cur[i]].v){

                    if(f>edge[cur[i]].cap){

                        f=edge[cur[i]].cap;

                        pos=i;

                    }

                }

                for(i=s;i!=t;i=edge[cur[i]].v){

                    edge[cur[i]].cap-=f;

                    edge[cur[i]^].cap+=f;

                }

                flow+=f;

                if(flow>=n)

                    return flow;

                u=pos;

            }

            for(i=cur[u];i!=-;i=edge[i].next)

                if(d[edge[i].v]+==d[u]&&edge[i].cap)   break;

            if(i!=-){

                cur[u]=i;

                pre[edge[i].v]=u;

                u=edge[i].v;

            }

            else{

                if(--num[d[u]]==) break;

                int mind=nv;

                for(i=head[u];i!=-;i=edge[i].next){

                    if(mind>d[edge[i].v]&&edge[i].cap){

                        mind=d[edge[i].v];

                        cur[u]=i;

                    }

                }

                d[u]=mind+;

                num[d[u]]++;

                u=pre[u];

            }

        }

        return flow;

    }

}F;

int vis[];

int main()

{

    #ifndef ONLINE_JUDGE

        freopen("in.txt","r",stdin);

        freopen("out.txt","w",stdout);

    #endif

    int S,T,N,M,u,v,tmp,k;

    int op;

    while(scanf("%d%d",&N,&M)==){

        F.init();

        k=;

        memset(vis,,sizeof(vis));

        for(int i=;i<=N;++i){

            int x=;

            for(int j=;j<=M;++j){

                scanf("%d",&op);

                x<<=;

                x+=op;                      //转换为二进制状态

            }

            vis[x]++;

        }

        for(int i=;i<=;++i) if(vis[i]) k++;        //记录缩点后点数

        S=;T=k+M+; F.nv=k+M+,F.n = N;

        int id=;

        for(int i=;i<=;++i){

            if(!vis[i]) continue;

            id++;

            int sta = i,cnt = vis[i];

            for(int j=,t=;j<=sta;j<<=,t++){

                if(j&sta) F.AddEdge(id,t+k,INF);

            }

            F.AddEdge(S,id,cnt);

        }

        for(int i=;i<=M;++i){

            scanf("%d",&tmp);

            F.AddEdge(i+k,T,tmp);

        }

        if(F.isap(S,T)==N) printf("YES\n");

        else printf("NO\n");

    }

    return ;

}

还有一种做法是二分图多重匹配。二分图多重匹配的思路与匈牙利算法接近，也是从以匹配的点中寻找增广路。X部为N个人，Y部为M个星球，每个星球有自己的匹配上限。在时间上，两种实现方法所差不多。

#include<iostream>

#include<stdio.h>

#include<cmath>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

typedef long long LL;

const int maxn = 1e5+,maxm = 2e6+;

int N,M;

struct Node{

    int K[];

}link[maxn];

int cnt[];

struct Edge{

    int to,next;

}edges[maxm];

int head[maxn],tot;

bool used[];

int limit[];

void init()

{

    tot=;

    memset(head,-,sizeof(head));

}

void AddEdge(int u,int v)

{

    edges[tot].to = v;

    edges[tot].next = head[u];

    head[u] = tot++;

}

bool dfs(int u){

    int v;

    for(int i=head[u];~i;i = edges[i].next){

        v = edges[i].to;

        if(!used[v]){

            used[v]=true;

            if(cnt[v]<limit[v]){

                link[v].K[cnt[v]++]=u;

                return true;

            }

            for(int j=;j<cnt[v];++j){

                if(dfs(link[v].K[j])){

                    link[v].K[j]=u;

                    return true;

                }

            }

        }

    }

    return false;

}

bool hungary(){

    memset(cnt,,sizeof(cnt));

    for(int u=;u<=N;u++){

        memset(used,,sizeof(used));

        if(!dfs(u)) return false;     //只要有一个人不能匹配则失败

    }

    return true;

}

int main()

{

    #ifndef ONLINE_JUDGE

        freopen("in.txt","r",stdin);

        freopen("out.txt","w",stdout);

    #endif

    int T,u,v,tmp,k;

    int op;

    while(scanf("%d%d",&N,&M)==){

        init();

        for(int i=;i<=N;++i){

            for(int j=;j<=M;++j){

                scanf("%d",&op);

                if(op) AddEdge(i,j);

            }

        }

        for(int i=;i<=M;++i) scanf("%d",&limit[i]);

        if(hungary()) printf("YES\n");

        else printf("NO\n");

    }

    return ;

}

巴特西

HDU - 3605 Escape (缩点+最大流/二分图多重匹配)

最新文章

热门文章