Hdu 3488 Tour (KM 有向环覆盖)

题目链接：

　　Hdu 3488 Tour

题目描述：

　　有n个节点，m条有权单向路，要求用一个或者多个环覆盖所有的节点。每个节点只能出现在一个环中，每个环中至少有两个节点。问最小边权花费为多少？

解题思路：

　　因为每个节点就出现一个，那么每个节点出度和入度都为1咯。我们可以对每个节点u拆点为u,u'，分别放在集合X,Y.然后对两个集合进行完备匹配。完备匹配成功以后，每个节点就会有只有一个出度，一个入度的。

用KM求最小匹配的话，先初始化maps为-INF，然后把各边权值存为负，求出最大值取反即可。

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 const int maxn = ;

 const int INF = 0x3f3f3f3f;

 int maps[maxn][maxn], used[maxn], s[maxn], n;

 int lx[maxn], ly[maxn];

 bool visx[maxn], visy[maxn];

 bool Find (int x)

 {

     visx[x] = ;

     for (int i=; i<=n; i++)

     {

         if (!visy[i] && lx[x]+ly[i]==maps[x][i])

         {

             visy[i] = ;

             if (!used[i] || Find(used[i]))

             {

                 used[i] = x;

                 return true;

             }

         }

         else

             s[i] = min (s[i], lx[x] + ly[i] - maps[x][i]);

     }

     return false;

 }

 int KM ()

 {

     memset (used, , sizeof(used));

     memset (lx, , sizeof(lx));

     memset (ly, , sizeof(ly));

     for (int i=; i<=n; i++)

         for (int j=; j<=n; j++)

             lx[i] = max (lx[i], maps[i][j]);

     for (int i=; i<=n; i++)

     {

         for (int j=; j<=n; j++)

             s[j] = INF;

         while ()

         {

             memset (visx, , sizeof(visx));

             memset (visy, , sizeof(visy));

             if (Find(i))

                 break;

             int d = INF;

             for (int j=; j<=n; j++)

                 if (!visy[j])

                     d = min (s[j], d);

             for (int j=; j<=n; j++)

             {

                 if (visx[j])

                     lx[j] -= d;

                 if (visy[j])

                     ly[j] += d;

             }

         }

     }

     int res = ;

     for (int i=; i<=n; i++)

         res += maps[used[i]][i];

     return res;

 }

 int main ()

 {

     int m, t;

     scanf ("%d", &t);

     while (t --)

     {

         scanf("%d %d", &n, &m);

         for (int i=; i<=n; i++)

             for (int j=; j<=n; j++)

                 maps[i][j] = -INF;

         while (m --)

         {

             int u, v, s;

             scanf ("%d %d %d", &u, &v, &s);

             maps[u][v] = max(maps[u][v], -s;

         }

         printf ("%d\n", -KM());

     }

     return ;

 }