[luoguP2764] 最小路径覆盖问题（最大流 || 二分图最大匹配）

传送门

可惜洛谷上没有special judge，不然用匈牙利也可以过的，因为匈牙利在增广上有一个顺序问题，所以没有special judge就过不了了。

好在这个题的测试数据比较特殊，如果是网络流的话按照顺序加边，就可以过。

最小不相交路径覆盖 = 总点数 最大匹配数

——代码

1 #include <queue> 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #define N 20001 6 #define min(x, y) ((x) < (y) ? (x) : (y)) 7 #define max(x, y) ((x) > (y) ? (x) : (y)) 8 9 int n, m, cnt, sum, s, t; 10 int head[N], belong[N], to[N], next[N], val[N], suc[N], cur[N], dis[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 70 } 71 return ret; 72 } 73 74 int main() 75 88 for(i = 1; i <= n; i++) 89 95 while(bfs()) 96 100 for(i = 1; i <= n; i++) 101 if(suc[i]) 102 111 puts(""); 112 } 113 printf("%d\n", n sum); 114 return 0; 115 }
View Code

上一篇：[luoguP2762] 太空飞行计划问题（最大权闭合图—最小割—最大流）

下一篇：[luoguP2765] 魔术球问题（最大流—最小不相交路径覆盖）

---

二分图 最大匹配 最大流 网络流 最小路径覆盖 匈牙利算法