POJ 2594 Treasure Exploration 最小可相交路径覆盖

DAG的最小可相交路径覆盖：

算法：先用floyd求出原图的传递闭包，即如果a到b有路径，那么就加边a->b。然后就转化成了最小不相交路径覆盖问题。

这里解释一下floyd的作用如果1->2->3->4那么1可以到达2，3，4只要需要借助一些点，那么就可以直接把1与2，3，4相连，这就是floyd要做的事。

证明：为了连通两个点，某条路径可能经过其它路径的中间点。比如1->3->4，2->4->5。但是如果两个点a和b是连通的，只不过中间需要经过其它的点，那么可以在这两个点之间加边，那么a就可以直达b，不必经过中点的，那么就转化成了最小不相交路径覆盖。

POJ 2594题意：

首先给你一个DAG，你需要派机器人到达某个宝藏的位置，然后机器人可以沿着道路走下去。这些宝藏可以被多个机器人到达。问至少需要多少个机器人

可以把所有宝藏位置都探索一边

题解：

如果把宝藏当作顶点，首先我们可以判断某些顶点可能不止使用一次。这道题的一部分和这道题很相似，这里都不复述了。同样也需要用到拆点操作

知道拆点和最小不相交路径覆盖就可以解决了

代码：

 1 #include<stdio.h>

 2 #include<algorithm>

 3 #include<string.h>

 4 #include<iostream>

 5 #include<queue>

 6 #include<vector>

 7 using namespace std;

 8 const int maxn=510;

 9 int n,match[maxn],visit[maxn],v[maxn][maxn];

10 int floyd()  //就光多了这一个函数

11 {

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

13     {

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

15         {

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

17             {

18                 if(v[i][k] && v[k][j])

19                     v[i][j]=1;

20             }

21         }

22     }

23 }

24 int dfs_solve(int x)

25 {

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

27     {

28         if(v[x][i] && !visit[i])

29         {

30             visit[i]=1;

31             if(match[i]==0 || dfs_solve(match[i]))

32             {

33                 match[i]=x;

34                 return 1;

35             }

36         }

37     }

38     return 0;

39 }

40 int hungran()

41 {

42     int ans=0;

43     memset(match,0,sizeof(match));

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

45     {

46         memset(visit,0,sizeof(visit));

47         ans+=dfs_solve(i);

48     }

49     return ans;

50 }

51 int main()

52 {

53     int m;

54     while(~scanf("%d%d",&n,&m))

55     {

56         if(!n && !m) break;

57         memset(v,0,sizeof(v));

58         while(m--)

59         {

60             int u,vv;

61             scanf("%d%d",&u,&vv);

62             v[u][vv]=1;

63         }

64         floyd();

65         printf("%d\n",n-hungran());

66     }

67     return 0;

68 }

巴特西

POJ 2594 Treasure Exploration 最小可相交路径覆盖

最新文章

热门文章