HUD3488 Tour(二分图的最小权值和)

题意：

给你一个有向图，边有权值，现在要你求若干个环包含所有的顶点，并且每个顶点只出现一次（除了起点），求所有环中所有边得权值之和最小值。

要点：

因为每个顶点只出现一次，干脆所有环都拆成起点到一个点再回起点，这样就是一个二分图的最小权值和问题。前面做的题都是求最大权值和，最小权值和就是将每条边的权值取负，其他的都不用变（除了lx的取最大值），最后输出再取负即可。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 205
#define inf 0x3f3f3f3f
bool sx[N], sy[N];
int lx[N], ly[N],w[N][N],girl[N];
int slack[N];
int n, m;void init()
{for (int i = 0; i < N; i++)for (int j = 0; j < N; j++)w[i][j] = -inf;
}
bool find(int u)
{int v, t;sx[u] = true;for (v = 1; v <= n; v++){if (sy[v])continue;t = lx[u] + ly[v] - w[u][v];if (t == 0){sy[v] = true;if (girl[v] == -1 || find(girl[v])){girl[v] = u;return true;}}elseslack[v] = min(slack[v], t);}return false;
}
int km()
{int i,j;memset(girl, -1, sizeof(girl));memset(ly, 0, sizeof(ly));for (int i = 1; i <= N; ++i){//lx[i] = -inf;注意最大权的模板中的这里不用写for (int j = 1; j <= N; ++j)lx[i] = max(lx[i], w[i][j]);}for (i = 1; i <= n; i++){memset(slack, inf, sizeof(slack));while (1){memset(sx, false, sizeof(sx));memset(sy, false, sizeof(sy));if (find(i))break;int d = inf;for (j = 1; j <= n; j++)if (!sy[j])d = min(d, slack[j]);for (j = 1; j <= n; j++)if (sx[j])lx[j] -= d;for (j = 1; j <= n; j++){if (sy[j])ly[j] += d;elseslack[j] -= d;}}}int sum = 0;for (i = 1; i <= n; i++)if (girl[i] != -1)sum += w[girl[i]][i];return sum;
}int main()
{int t,x,y,value;scanf("%d", &t);while (t--){init();scanf("%d%d", &n, &m);while (m--){scanf("%d%d%d", &x, &y, &value);w[x][y] = max(w[x][y], -value);//求最小权值就直接把权值改成负数求最大即可}printf("%d\n", -km()); //最后取负输出即可}return 0;
}