285484026

「网络流 24 题」圆桌聚餐
「网络流 24 题」圆桌聚餐题解:从源点向每个单位连接容量为单位人数的边,从每个饭桌向汇点连接容量为饭桌大小的边,...
扫描右侧二维码阅读全文
05
2018/10

「网络流 24 题」圆桌聚餐

「网络流 24 题」圆桌聚餐
题解:从源点向每个单位连接容量为单位人数的边,从每个饭桌向汇点连接容量为饭桌大小的边,从每个单位向每个饭桌连接容量为1的边。在这个二分图上跑出来的最大流等于单位人数的总和,那么存在可行解
方案输出:从看每个单位的满流边连向的饭桌就坐着自己公司的员工

#include <bits/stdc++.h>

const int MAXN = 100000,INF = 1000000;

using namespace std;

int m,n,e = 2,s,t,ans,sum;
int cur[MAXN],d[MAXN],head[MAXN];

vector<int>table[MAXN];

struct node{
    int v,c,f,next;
}edge[MAXN];

inline void addedge(int u,int v,int w){
    edge[e] = (node){v,w,0,head[u]};head[u] = e++;
    edge[e] = (node){u,0,0,head[v]};head[v] = e++;
}

inline void init(){
    scanf("%d%d",&n,&m);
    s = 0;t = n+m+1;
    int v;
    for(int i = 1;i <= n;i++){
        scanf("%d",&v);
        sum += v;
        addedge(s,i,v);
    }
    
    for(int i = 1;i <= m;i++){
        scanf("%d",&v);
        addedge(i+n,t,v);
    }
    
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= m;j++)
            addedge(i,j+n,1);    
}

queue<int>Q;

inline bool bfs(){
    memset(d,0,sizeof(d));
    Q.push(s);d[s] = 1;
    while(!Q.empty()){
        int x = Q.front();Q.pop();
        for(int i = head[x];i;i = edge[i].next){
            node E = edge[i];
            if(!d[E.v] && E.c > E.f){
                d[E.v] = d[x] + 1;
                Q.push(E.v);
            }
        }
    }
    return d[t] ? true : false;
}

int dfs(int x,int a){
    if(x == t || a == 0) return a;
    int flow = 0,f;
    for(int &i = cur[x];i;i = edge[i].next){
        node &E = edge[i];
        if(d[E.v] == d[x] + 1 && (f = dfs(E.v,min(E.c-E.f,a))) > 0){
            E.f += f;
            edge[i^1].f -= f;
            a -= f;
            flow += f;
            if(a == 0) break;
        }
    }
    return flow;
}

inline int max_flow()
{
    int flow = 0;
    while(bfs()){
        for(int i = s;i <= t;i++) cur[i] = head[i];
        flow += dfs(s,INF);
    }
    return flow;
}

int main()
{
    #ifdef hi_archer
      freopen("input.txt", "r", stdin);
    #endif
    init();
    ans = max_flow();
    if(ans != sum){printf("0\n");return 0;}
    else printf("1\n");
    for(int i = 1;i <= n;i++)
        for(int j = head[i];j;j = edge[j].next)
            if(edge[j].c == edge[j].f)
                table[i].push_back(edge[j].v-n);
        
    for(int i = 1;i <= n;i++) sort(table[i].begin(),table[i].end());
    
    for(int i = 1;i <= n;i++){
        for(int j = 0;j < table[i].size();j++)    printf("%d ",table[i][j]);
        printf("\n");
    }
    
    return 0;
} 
Last modification:October 5th, 2018 at 03:02 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment