首页 > 代码库 > [cogs729]圆桌问题（最大流）
[cogs729]圆桌问题（最大流）
传送门
模型
二分图多重匹配问题，可以用最大流解决。
实现
建立二分图，每个单位为X集合中的顶点，每个餐桌为Y集合中的顶点，增设附加源S和汇T。
1、从S向每个Xi顶点连接一条容量为该单位人数的有向边。
2、从每个Yi顶点向T连接一条容量为该餐桌容量的有向边。
3、X集合中每个顶点向Y集合中每个顶点连接一条容量为1的有向边。
求网络最大流，如果最大流量等于所有单位人数之和，则存在解，否则无解。对于每个单位，从X集合对应点出发的所有满流边指向的Y集合的顶点就是该单位人员的安排情况（一个可行解）。
分析
对于一个二分图，每个顶点可以有多个匹配顶点，称这类问题为二分图多重匹配问题。X，Y集合之间的边容量全部是1，保证两个点只能匹配一次（一个餐桌上只能有一个单位的一个人），源
汇的连边限制了每个点匹配的个数。求出网络最大流，如果流量等于X集合所有点与S边容量之和，那么则说明X集合每个点都有完备的多重匹配。
注意 cogs 需要写文件！
——代码
1 #include <queue> 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #define N 50001 6 #define M 5000001 7 #define min(x, y) ((x) < (y) ? (x) : (y)) 8 9 int n, m, cnt, sum, ans, s, t; 10 int head[N], to[M], val[M], next[M], dis[N], cur[N]; 11 12 inline int read() 13 { 14 int x = 0, f = 1; 15 char ch = getchar(); 16 for(; !isdigit(ch); ch = getchar()) if(ch == ‘-‘) f = -1; 17 for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - ‘0‘; 18 return x * f; 19 } 20 21 inline void add(int x, int y, int z) 22 { 23 to[cnt] = y; 24 val[cnt] = z; 25 next[cnt] = head[x]; 26 head[x] = cnt++; 27 } 28 29 inline bool bfs() 30 { 31 int i, u, v; 32 std::queue <int> q; 33 memset(dis, -1, sizeof(dis)); 34 q.push(s); 35 dis[s] = 0; 36 while(!q.empty()) 37 { 38 u = q.front(), q.pop(); 39 for(i = head[u]; i ^ -1; i = next[i]) 40 { 41 v = to[i]; 42 if(val[i] && dis[v] == -1) 43 { 44 dis[v] = dis[u] + 1; 45 if(v == t) return 1; 46 q.push(v); 47 } 48 } 49 } 50 return 0; 51 } 52 53 inline int dfs(int u, int maxflow) 54 { 55 if(u == t) return maxflow; 56 int v, d, ret = 0; 57 for(int &i = cur[u]; i ^ -1; i = next[i]) 58 { 59 v = to[i]; 60 if(val[i] && dis[v] == dis[u] + 1) 61 { 62 d = dfs(v, min(val[i], maxflow - ret)); 63 ret += d; 64 val[i] -= d; 65 val[i ^ 1] += d; 66 if(ret == maxflow) return ret; 67 } 68 } 69 return ret; 70 } 71 72 int main() 73 { 74 freopen("roundtable.in","r",stdin); 75 freopen("roundtable.out","w",stdout); 76 int i, j, x; 77 m = read(); 78 n = read(); 79 s = 0, t = n + m + 1; 80 memset(head, -1, sizeof(head)); 81 for(i = 1; i <= m; i++) 82 { 83 sum += x = read(); 84 add(s, i, x), add(i, s, 0); 85 for(j = 1; j <= n; j++) 86 add(i, j + m, 1), add(j + m, i, 0); 87 } 88 for(i = 1; i <= n; i++) 89 { 90 x = read(); 91 add(i + m, t, x), add(t, i + m, 0); 92 } 93 while(bfs()) 94 { 95 for(i = s; i <= t; i++) cur[i] = head[i]; 96 ans += dfs(s, 1e9); 97 } 98 if(ans ^ sum) 99 {100 puts("0");101 return 0;102 }103 puts("1");104 for(i = 1; i <= m; puts(""), i++)105 for(j = head[i]; j ^ -1; j = next[j])106 if(!val[j])107 printf("%d ", to[j] - m); 108 return 0;109 }
[cogs729]圆桌问题（最大流）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。