本文主要是介绍hdu - 3488 - Tour（二分图最佳完美匹配），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：N个点，M条边的有向图，边有正权，求使每个点至少属于一个环的路径的最小权和（2 <= N <= 200，M <= 30000，0 < 每个边权W <= 10000）。
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3488
——>>好题～拆点的二分图最佳完美匹配。
对于每一个顶点u，将其拆成u1和u2，若原来有一条边为u——>v，则变成u2——>v1，以xx2为X结点，xx1为Y结点，边权的相反数为权值（我们要求最小权和，二分图最佳完美匹配KM求的是最大权和，所以取边权的相反数作为权值，即可直接调用KM），跑一次KM，根据fa[]（即选出来的路径）输出就好。不确定是否有重边的情况，为保险，插入权值时加个比较～
#include <cstdio>
#include <algorithm>using namespace std;const int maxn = 200 + 10;
const int INF = 0x3f3f3f3f;int N, M, w[maxn][maxn], lx[maxn], ly[maxn], fa[maxn];
bool S[maxn], T[maxn];bool match(int i){S[i] = 1;for(int j = 1; j <= N; j++) if(lx[i] + ly[j] == w[i][j] && !T[j]){T[j] = 1;if(!fa[j] || match(fa[j])){fa[j] = i;return 1;}}return 0;
}void update(){int a = INF;for(int i = 1; i <= N; i++) if(S[i])for(int j = 1; j <= N; j++) if(!T[j])a = min(a, lx[i] + ly[j] - w[i][j]);for(int i = 1; i <= N; i++){if(S[i]) lx[i] -= a;if(T[i]) ly[i] += a;}
}void KM(){for(int i = 1; i <= N; i++) fa[i] = lx[i] = ly[i] = 0;for(int i = 1; i <= N; i++)while(1){for(int j = 1; j <= N; j++) S[j] = T[j] = 0;if(match(i)) break;else update();}
}void read(){int U, V, W;scanf("%d%d", &N, &M);for(int i = 1; i <= N; i++)for(int j = 1; j <= N; j++) w[i][j] = -INF;for(int i = 1; i <= M; i++){scanf("%d%d%d", &U, &V, &W);w[U][V] = max(w[U][V], -W);}
}void solve(){int sum = 0;for(int i = 1; i <= N; i++) sum += w[fa[i]][i];printf("%d\n", -sum);
}int main()
{int C;scanf("%d", &C);while(C--){read();KM();solve();}return 0;
}
这篇关于hdu - 3488 - Tour（二分图最佳完美匹配）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
