洛谷模板题
学了匈牙利算法。
匈牙利算法核心是找增广路经。
可以求出二分图的最大匹配数。
感觉还是挺好理解的。
时间复杂度 邻接矩阵： 邻接表：
空间复杂度 邻接矩阵： 邻接表：
看的这个blog，有些恶趣味。（受不了凤姐那张图。。）
——代码
1 #include <cstdio> 2 #include <cstring> 3 4 using namespace std; 5 6 int n, m, k, cp, cnt; 7 int girl[10010], to[1000001], next[1000001], head[10010]; 8 //girl[i]记录第i个girl所属的boy 9 bool dog[10010]; 10 //dog[i]记录i是否脱单 11 12 inline void add(int x, int y) 13 18 19 int find_girl(int u) 20 34 } 35 } 36 return 0; 37 } 38 39 int main() 40 50 for(i = 1; i <= n; i++) 51 55 printf("%d", cp); 56 return 0; 57 }View Code
PS:不要在意变量名函数名这些细节。。
但是感觉匈牙利算法好TM慢啊，所以还是学了dinic，用网络流做好了（深搜版isap会超时，日了狗）。
就是再加一个超级源点s连接集合X的点，和一个超级汇点t连接Y的点。
求s到t的最大流就好。
（这个题集合X和集合Y即使数相同也是两个独立的所以得加一个偏移量，还有测试数据表示看不懂了。）
——代码
1 #include <cstdio> 2 #include <cstring> 3 #include <queue> 4 5 using namespace std; 6 7 int n, m, cnt, ans, e; 8 int head[100001], to[2000001], val[2000001], next[2000001], dis[100001], cur[100001]; 9 10 void add(int x, int y, int z) 11 17 18 int dfs(int u, int t, int maxflow) 19 34 } 35 return ret; 36 } 37 38 bool bfs(int s, int t) 39 58 } 59 } 60 return 0; 61 } 62 int main() 64 75 for(i = 1; i <= m; i++) 76 80 for(i = 1; i <= e; i++) 81 87 while(bfs(s, t)) 88 92 printf("%d", ans); 93 return 0; 94 }View Code
上一篇：[HAOI2006]受欢迎的牛（tarjan缩点）
下一篇：公路修建（Prim）
二分图 模板 最大流 匈牙利算法 最大匹配
