dfs 更好写，bfs 复杂度保证
by Coros_Trusds @ 2022-08-04 18:06:19
dfs好像是 $O(n^{2}m)$,bfs 是 $O(n^{3})$,也就是边多的时候bfs快，边少的时候dfs快
by Aisaka_Taiga @ 2022-08-04 18:09:25
@[yi_fan0305](/user/715213) dfs-KM 和 bfs-KM 都是 $O(n^3)$ 复杂度的
by 智子 @ 2022-08-04 18:38:23
@[yi_fan0305](/user/715213)
这是 dfs-KM AC 洛谷模板题（数据较强）的 AC 记录和代码
<https://www.luogu.com.cn/record/72937743>
```cpp
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 500 + 5;
const long long INF = 1e18;
long long e[MAXN][MAXN], la[MAXN], lb[MAXN], slack[MAXN];
int match[MAXN], last[MAXN];
bool va[MAXN], vb[MAXN];
int n, m;
bool dfs(int u, int fa) {
va[u] = true;
for(int v = 1; v <= n; v++) {
if(vb[v]) continue;
if(la[u] + lb[v] == e[u][v]) {
vb[v] = true;
last[v] = fa;
if(!match[v] || dfs(match[v], v)) {
match[v] = u;
return true;
}
} else if(slack[v] > la[u] + lb[v] - e[u][v]) {
slack[v] = la[u] + lb[v] - e[u][v];
last[v] = fa;
}
}
return false;
}
long long KM() {
for(int i = 1; i <= n; i++) {
la[i] = -INF;
lb[i] = 0;
for(int j = 1; j <= n; j++) {
la[i] = max(la[i], e[i][j]);
}
}
for(int i = 1; i <= n; i++) {
fill(va + 1, va + n + 1, false);
fill(vb + 1, vb + n + 1, false);
fill(slack + 1, slack + n + 1, INF);
int st = 0; match[st] = i;
while(match[st]) {
if(dfs(match[st], st)) break;
long long delta = INF;
for(int j = 1; j <= n; j++) {
if(!vb[j] && delta > slack[j]) {
delta = slack[j];
st = j;
}
}
for(int j = 1; j <= n; j++) {
if(va[j]) la[j] -= delta;
if(vb[j]) lb[j] += delta; else slack[j] -= delta;
}
vb[st] = true;
}
while(st) {
match[st] = match[last[st]];
st = last[st];
}
}
long long ans = 0;
for(int i = 1; i <= n; i++) {
ans += e[match[i]][i];
}
return ans;
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
e[i][j] = -INF;
}
}
for(int i = 1; i <= m; i++) {
int u, v;
long long w;
scanf("%d%d%lld", &u, &v, &w);
e[u][v] = max(e[u][v], w);
}
printf("%lld\n", KM());
for(int i = 1; i <= n; i++) {
printf("%d ", match[i]);
}
printf("\n");
return 0;
}
```
by 智子 @ 2022-08-04 18:39:47
@[Coros_Trusds](/user/430409) 这两个写法都有复杂度保证
by 智子 @ 2022-08-04 18:40:07
@[yi_fan0305](/user/715213) dfs 写法确实更好些一些
by 智子 @ 2022-08-04 18:40:41
@[Coros_Trusds](/user/430409)
<https://www.luogu.com.cn/record/72656301>
<https://www.luogu.com.cn/record/72937743>
上为 BFS 写法，下为 DFS 写法，两种写法的运行时间几乎没有区别
by 智子 @ 2022-08-04 18:42:07
@[Coros_Trusds](/user/430409) 两种写法的复杂度相同，常数也基本相同
by 智子 @ 2022-08-04 18:43:02
@[智子](/user/132435) ? dfs 可以过模板题了？之前我写的时候 T 了。。
by Coros_Trusds @ 2022-08-04 18:55:30