传送门
可惜洛谷上没有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
上一篇：[luoguP2031] 脑力达人之分割字串（DP）
下一篇：[luoguP2280] [HNOI2003]激光炸弹（DP）
匈牙利算法 最大流 网络流 最大匹配 最小路径覆盖 二分图
