「网络流 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;
}