运动员最佳匹配问题（km算法）

洛谷传送门

带权二分图最大权完美匹配。

裸的km算法。

注意开long long。

1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 5 using namespace std; 6 7 const long long INF = 99999999999999999; 8 int n, match[21]; 9 long long p[21][21], q[21][21], love[21][21], ex_boy[21], ex_girl[21], slack[21]; 10 bool vis_boy[21], vis_girl[21]; 11 12 bool find(int i) 13 29 } 30 else slack[j] = min(slack[j], gap); 31 } 32 return 0; 33 } 34 35 long long KM() 36 60 } 61 } 62 for(i = 1; i <= n; i++) ret += love[match[i]][i]; return ret; 64 } 65 66 int main() 67
View Code

上一篇：【模板】网络最大流

下一篇：【模板】树链剖分

---

二分图 最大权完美匹配 KM算法