[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 20 21 inline void add(int x, int y, int z) 22 28 29 inline bool bfs() 30 48 } 49 } 50 return 0; 51 } 52 53 inline int dfs(int u, int maxflow) 54 68 } 69 return ret; 70 } 71 72 int main() 73 88 for(i = 1; i <= n; i++) 89 93 while(bfs()) 94 98 if(ans ^ sum) 99 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 }
View Code

上一篇：[luoguP2770] 航空路线问题（最小费用最大流）

下一篇：[luoguP1251] 餐巾计划问题（费用流）

---

最大流 网络流