[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 24 } 25 return 0; 26 } 27 28 int main() 29 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 50 printf("%d\n", n ans); 51 } 52 }
View Code

上一篇：[luoguP2184] 贪婪大陆（树状数组）

下一篇：[luoguP1077] 摆花（DP）

---

二分图 Floyd 最小路径覆盖 匈牙利算法