题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3488
题意是有n个城市,m条边,这个图中有一个或者多个环,问要覆盖所有的点,选那几个环的总权值最小。
因为是有向环,所以每个点的入度和出度都是1,所以就符合了二分图的性质,我们就需要把每个点拆成两个点,一个表示入度一个表示出度,然后求二分图的最佳匹配就行了,因为要求权值的最小和,我们就需要把权值取负数,然后计算最大权,然后再对结果取负就好了。
AC代码:
#include <bits/stdc++.h>
#define maxn 305
#define inf 0x7fffffff
using namespace std;
int w[maxn][maxn];
int pre[maxn], cx[maxn], cy[maxn];
bool usex[maxn], usey[maxn];
int n,m,ans;
void init(){
memset(cy, 0, sizeof(cy));
memset(cx, 0, sizeof(cx));
memset(w, -0x3f3f, sizeof(w));
memset(pre, -1, sizeof(pre));
}
bool dfs(int u){
usex[u] = true;
for(int v=1;v<=n;v++){
if(usey[v] == false && cx[u] + cy[v] == w[u][v]){
usey[v] = true;
if(pre[v] == -1 || dfs(pre[v])){
pre[v] = u;
return true;
}
}
}
return false;
}
int km(){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cx[i] = max(cx[i], w[i][j]);
}
}
for(int i=1;i<=n;i++){
while(true){
int d = inf;
memset(usex, false, sizeof(usex));
memset(usey, false, sizeof(usey));
if( dfs(i) ) break;
for(int j=1;j<=n;j++){
if(usex[j] == true){
for(int k=1;k<=n;k++){
if(usey[k] == false) d = min(d, cx[j] + cy[k] - w[j][k]);
}
}
}
if(d == inf) return -1;
for(int j=1;j<=n;j++) if(usex[j] == true) cx[j] -= d;
for(int j=1;j<=n;j++) if(usey[j] == true) cy[j] += d;
}
}
ans = 0;
for(int i=1;i<=n;i++){
ans += w[pre[i]][i];
}
return ans;
}
int main()
{
int T;
scanf("%d",&T);
while(T--){
init();
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
int u,v,ww;
scanf("%d%d%d",&u,&v,&ww);
w[u][v] = max(w[u][v], -ww);
}
printf("%d\n", -km());
}
return 0;
}