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

淩亂°似流年 2023-10-11 09:36 5阅读 0赞

[最小路径覆盖][Link 1]

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，你需要派机器人到达某个宝藏的位置，然后机器人可以沿着道路走下去。这些宝藏可以被多个机器人到达。问至少需要多少个机器人

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

题解：

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

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

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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 }

转载于:https://www.cnblogs.com/kongbursi-2292702937/p/11494436.html

[Link 1]: https://www.cnblogs.com/justPassBy/p/5369930.html
[Link 2]: https://www.cnblogs.com/kongbursi-2292702937/p/11493957.html
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif