网络流24题-圆桌问题

Ajsoabk · 2019-02-02 14:17:47 · 题解

网络流24题-圆桌问题

本题要求m个部门的人与n个圆桌的匹配,满足每个部门人最多只能有一个人在某个桌上

部门做左部集,圆桌做右部集,

每个部门与每个圆桌连容量为1的边

这样跑出的流就保证一个部门在一个圆桌上的人不超过一个

部门的人数就是s向部门的容量

圆桌的人数就是圆桌向t的容量

而由于圆桌的位子可能有多,但每个人都必须有位子

故由s连出的容量之和必小于等于圆桌连向t的容量之和

所以最大流是否等于人数之和就代表了是否有解

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int M=200;
const int N=300;
const int inf=0x7fffffff;
template<class T>inline void read(T &num){
    char ch;
    while(!isdigit(ch=getchar()));
    num=ch-'0';
    while(isdigit(ch=getchar()))num=num*10+ch-'0';
}

int hea[M+N],to[N*M<<1],nex[N*M<<1],val[N*M<<1],dep[N+M],tot=1,n,m,s,t;

inline void add_edge(const int x,const int  y,const int w){
    to[++tot]=y,nex[tot]=hea[x],hea[x]=tot,val[tot]=w;
}

inline void Add_edge(const int x,const int y,const int w){
//printf("%d --> %d(%d)\n",x,y,w);
    add_edge(x,y,w);
    add_edge(y,x,0);
}

queue<int> que;
bool bfs(){
//printf("!\n");
    memset(dep,0,sizeof(dep));
    dep[s]=1;
    while(que.size())que.pop();
    que.push(s);
    int x;
    while(que.size()){
        x=que.front();que.pop();
        for(int i=hea[x];i;i=nex[i]){
            int y=to[i];
            if(val[i]&&!dep[y]){
                dep[y]=dep[x]+1;
//printf("%d -> %d\n",x,y);
//if(y==t)printf("return true\n");
                if(y==t)return true;
                que.push(y);
            }
        }
    }
    return false;
}

int dfs(const int x,const int flow){
//printf("dfs(%d,%d)\n",x,flow);
    if(x==t)return flow;
    int rest=flow,k;
    for(int i=hea[x];i&&rest;i=nex[i]){
        int y=to[i];
        if(val[i]&&dep[y]==dep[x]+1){
            k=dfs(y,min(rest,val[i]));
            if(k){
                val[i]-=k;
                val[i^1]+=k;
                rest-=k;
            }
            else dep[y]=0;
        }
    }
//printf("return %d\n",flow-rest);
    return flow-rest;
}

int dinic(){
    int maxflow=0,flow;
    while(bfs())while(flow=dfs(s,inf))maxflow+=flow;
//printf("return maxflow=%d\n",maxflow);
    return maxflow;
}

int ans;
int main(){
    read(m),read(n);
    s=n+m+1,t=s+1;
    for(int i=1,w;i<=m;++i){
        read(w);
        ans+=w;
        Add_edge(s,i,w);
    }
    for(int i=1,w;i<=n;++i){
        read(w);
        Add_edge(i+m,t,w);
    }
    for(int i=1;i<=m;++i)for(int j=1;j<=n;++j)Add_edge(i,j+m,1);
    if(dinic()==ans){
        printf("1\n");
        for(int i=1;i<=m;++i){
            for(int j=hea[i];j;j=nex[j]){
                int y=to[j];
                if(y<=m+n&&!val[j])printf("%d ",y-m);
            }
            printf("\n");
        }
    }
    else{
        printf("0\n");
    }
    return 0;
}