[POJ2594] Treasure Exploration（最小路径覆盖-传递闭包 + 匈牙利算法）

传送门

引子：

有一个问题，是对于一个图上的所有点，用不相交的路径把他们覆盖，使得每个点有且仅属于一条路径，且这个路径数量尽量小。

对于这个问题可以把直接有边相连的两点 x —> y，建一个二分图 x' —> y，最后节点数 - 最大匹配数即为最终答案。

这才是题解：

但是这个题目不同，此题问的是用一些路径把所有点覆盖，并没有说每个点有且仅属于一条路径，所以需要求这个图的传递闭包。

把可达的两点建立二分图。最后节点数 - 最大匹配数即为最终答案。

可以看看这篇blog

——代码

 1 #include <cstdio>
 2 #include <cstring>
 3 #define M(x, a) memset(a, x, sizeof(a));
 4 
 5 using namespace std;
 6 
 7 const int MAXN = 1001;
 8 int n, m, ans, cnt;
 9 int belong[MAXN];
10 bool a[MAXN][MAXN], vis[MAXN];
11 
12 inline bool find(int i)
13 {
14     int j;
15     for(j = 1; j <= n; j++)
16         if(!vis[j] && a[i][j])
17         {
18             vis[j] = 1;
19             if(!belong[j] || find(belong[j]))
20             {
21                 belong[j] = i;
22                 return 1;
23             }
24         }
25     return 0;
26 }
27 
28 int main()
29 {
30     int i, j, k, x, y;
31     while(scanf("%d %d", &n, &m) && n + m)
32     {
33         ans = 0;
34         M(0, a);
35         M(0, belong);
36         for(i = 1; i <= m; i++)
37         {
38             scanf("%d %d", &x, &y);
39             a[x][y] = 1;
40         }
41         for(k = 1; k <= n; k++)
42             for(i = 1; i <= n; i++)
43                 for(j = 1; j <= n; j++)
44                     a[i][j] = a[i][j] || (a[i][k] && a[k][j]);
45         for(i = 1; i <= n; i++)
46         {
47             memset(vis, 0, sizeof(vis));
48             if(find(i)) ans++;
49         }
50         printf("%d
", n - ans);
51     }
52 }

View Code