题目链接:HDU3488-Tour
题意:
n点,m条单向有权边,用一个或多个环去覆盖所有的点,要求经过边的权值和尽可能小。
题解:
二分图带权匹配。
把每个点拆为入点和出点,建立二分图,然后进行二分图带权匹配。
参考代码:
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
int T, n, m;
int nx, ny;
int dx[202], dy[202], match[202], slack[202], edge[202][202];
bool usedx[202], usedy[202];
bool dfs(int u)
{
usedx[u] = 1;
for (int i = 1; i <= ny; i++)
{
if (usedy[i])
continue;
if (dx[u] + dy[i] == edge[u][i])
{
usedy[i] = 1;
if (match[i] == -1 || dfs(match[i]))
{
match[i] = u;
return 1;
}
}
else
slack[i] = min(slack[i], dx[u] + dy[i] - edge[u][i]);
}
return 0;
}
int KM()
{
int sum = 0;
memset(dx, -inf, sizeof(dx));
memset(dy, 0, sizeof(dy));
memset(match, -1, sizeof(match));
for (int i = 1; i <= nx; i++)
{
for (int j = 1; j <= ny; j++)
{
dx[i] = max(edge[i][j], dx[i]);
}
}
for (int i = 1; i <= nx; i++)
{
memset(slack, 0x3f, sizeof(slack));
while (1)
{
memset(usedx, 0, sizeof(usedx));
memset(usedy, 0, sizeof(usedy));
if (dfs(i))
break;
int dis = inf;
for (int j = 1; j <= ny; j++)
if (!usedy[j])
dis = min(dis, slack[j]);
for (int j = 1; j <= n; j++)
{
if (usedx[j])
dx[j] -= dis;
if (usedy[j])
dy[j] += dis;
else
slack[j] -= dis;
}
}
}
for (int i = 1; i <= nx; i++)
sum += edge[match[i]][i];
return sum;
}
int main()
{
scanf("%d", &T);
while (T--)
{
scanf("%d%d", &n, &m);
memset(edge, -inf, sizeof(edge));
for (int i = 1; i <= m; i++)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
edge[u][v] = max(edge[u][v], -w);
}
nx = n, ny = n;
int ans = KM();
printf("%d\n", -ans);
}
return 0;
}