【模板】二分图匹配

洛谷模板题

学了匈牙利算法。

匈牙利算法核心是找增广路经。

可以求出二分图的最大匹配数。

感觉还是挺好理解的。

时间复杂度　　邻接矩阵：　　邻接表：

空间复杂度　　邻接矩阵：　　邻接表：

看的这个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

上一篇：doris单机安装部署

下一篇：人生第一次hash

---

二分图 最大匹配 最大流 模板 匈牙利算法