Poj 2594 Treasure Exploration (最小边覆盖+传递闭包)

时间：2022-10-06 17:28:39

题目链接：

　　Poj 2594 Treasure Exploration

题目描述：

　　在外星上有n个点需要机器人去探险，有m条单向路径。问至少需要几个机器人才能遍历完所有的点，一个点可以被多个机器人经过。

解题思路：

　　一眼看上去是普通的最小边覆盖，但是仔细想后发现如果在原图上进行最大匹配的话，每个点只能经过一次。这样的话对于本题求出的并不是最优解，所以我们要先对原图进行传递闭包处理，然后再进行最大匹配。

这个题目点数太少H_K和匈牙利算法在空间和时间上并没有什么差，就代码复杂度而言匈牙利算法更有优势。

 #include <iostream>//匈牙利算法

 #include <cstring>

 #include <queue>

 #include <cmath>

 #include <cstdio>

 using namespace std;

 const int maxn = ;

 int maps[maxn][maxn], n, m;

 int used[maxn], vis[maxn];

 void floyd ()

 {

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

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

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

                 if (maps[i][k] && maps[k][j])

                     maps[i][j] = ;

 }

 int Find (int u)

 {

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

     {

         if (!vis[i] && maps[u][i])

         {

             vis[i] = ;

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

             {

                 used[i] = u;

                 return ;

             }

         }

     }

     return ;

 }

 int main ()

 {

     while (scanf ("%d %d", &n, &m), n||m)

     {

         memset (maps, , sizeof(maps));

         while (m --)

         {

             int u, v;

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

             maps[u][v] = ;

         }

         floyd ();

         memset (used, , sizeof(used));

         int res = ;

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

         {

             memset (vis, , sizeof(vis));

             res += Find(i);

         }

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

     }

     return ;

 }
 #include <iostream>//H_K算法

 #include <cstring>

 #include <queue>

 #include <cmath>

 #include <cstdio>

 using namespace std;

 const int maxn = ;

 const int INF = 0x3f3f3f3f;

 int maps[maxn][maxn], n, m, dx[maxn], dy[maxn];

 int vis[maxn], cx[maxn], cy[maxn], dis;

 void floyd ()

 {

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

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

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

                 if (maps[i][k] && maps[k][j])

                     maps[i][j] = ;

 }

 bool bfs ()

 {

     queue <int> Q;

     dis = INF;

     memset (dx, -, sizeof(dx));

     memset (dy, -, sizeof(dy));

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

         if (cx[i] == -)

             {

                 Q.push(i);

                 dx[i] = ;

             }

     while (!Q.empty())

     {

         int u = Q.front();

         Q.pop();

         if (dx[u] > dis)

             break;

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

         {

             if (dy[i]==- && maps[u][i])

             {

                 dy[i] = dx[u] + ;

                 if (cy[i] == -)

                     dis = dy[i];

                 else

                 {

                     dx[cy[i]] = dy[i] +;

                     Q.push (cy[i]);

                 }

             }

         }

     }

     return dis != INF;

 }

 int dfs (int u)

 {

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

     {

         if (!vis[v] && dx[u]+==dy[v] && maps[u][v])

         {

             vis[v] = ;

             if (cy[v]!=- && dis==dy[v])

                 continue;

             if (cy[v]==- || dfs(cy[v]))

             {

                 cx[u] = v;

                 cy[v] = u;

                 return ;

             }

         }

     }

     return ;

 }

 int Max_match ()

 {

     int res = ;

     memset (cx, -, sizeof(cx));

     memset (cy, -, sizeof(cy));

     while (bfs())

     {

         memset (vis, , sizeof(vis));

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

             if (cx[i] == -)

                 res += dfs (i);

     }

     return res;

 }

 int main ()

 {

     while (scanf ("%d %d", &n, &m), n||m)

     {

         memset (maps, , sizeof(maps));

         while (m --)

         {

             int u, v;

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

             maps[u][v] = ;

         }

         floyd ();

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

     }

     return ;

 }

相关文章