题目链接：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;
}