最小路径覆盖

迷南。 2022-01-21 01:15 249阅读 0赞

转自：[https://blog.csdn.net/qq\_39627843/article/details/82012572][https_blog.csdn.net_qq_39627843_article_details_82012572]

花了好长时间，用于找了几篇能看懂的最小路径覆盖。

![70][]

**定义**：通俗点将，就是在一个有向图中，找出最少的路径，使得这些路径经过了所有的点。

最小路径覆盖分为**最小不相交路径覆盖**和**最小可相交路径覆盖**。

**最小不相交路径覆盖**：每一条路径经过的顶点各不相同。如图，其最小路径覆盖数为3。即1->3>4，2，5。

**最小可相交路径覆盖**：每一条路径经过的顶点可以相同。如果其最小路径覆盖数为2。即1->3->4，2->3>5。

特别的，每个点自己也可以称为是路径覆盖，只不过路径的长度是0。

大家要仔细想想上面的解释啊，这已经是我找到的最浅显的了。

而且一定要知道有这两种最小路径覆盖。

然后如果大家不知道匈利亚算法的，一定要去看看，还是比较简单的，就是一个dfs，连我都看的懂。

下面地址是关于匈利亚算法的详解，带图解，易懂

[https://blog.csdn.net/Arabic1666/article/details/79824390][https_blog.csdn.net_Arabic1666_article_details_79824390]

# DAG的最小不相交路径覆盖 #

**算法**：把原图的每个点V拆成VxVx和VyVy两个点，如果有一条有向边A->B，那么就加边Ax−>ByAx−>By。这样就得到了一个二分图。那么最小路径覆盖=原图的结点数-新图的最大匹配数。

**证明**：一开始每个点都是独立的为一条路径，总共有n条不相交路径。我们每次在二分图里找一条匹配边就相当于把两条路径合成了一条路径，也就相当于路径数减少了1。所以找到了几条匹配边，路径数就减少了多少。所以有最小路径覆盖=原图的结点数-新图的最大匹配数。

因为路径之间不能有公共点，所以加的边之间也不能有公共点，这就是匹配的定义。

说的拆点这么高深，其实操作起来超级超级简单，甚至没有操作。

简单的来说，每个顶点都能当成二分图中作为起点的顶点。

至于为什么答案是 n-ans，我谈谈我的理解

用dfs求的ans表示的意思是匹配数，换句话说，就是一条路连着的路径上的点的个数-1

![70][]

比如说这个图，我们用匈利亚算法，遍历每个点，发现1、3点可行，可匹配，而2、4、5都不能行。

如果我们单纯考虑1->3->5这条路径，有三个点，然后有两个点匹配了，我们用3减去2，就得到了1，这个1就是一个路径数，需要用1条路径来覆盖，再对剩下的2、4考虑，分别都需要一条路径来覆盖，因为2-0=0，2是顶点个数，0是匹配数。

所以，对于每条分路径，我们需要 v-cnt的路径来覆盖，最后将每个分路径合起来，我们得到n-cnt。

例题：[POJ1422][]

1.  `//`
2.  `// main.cpp`
3.  `// POJ1422最小不想交路径覆盖`
4.   
5.   
6.  `#include <iostream>`
7.  `#include <stdio.h>`
8.  `#include <string.h>`
9.  `#include <vector>`
10. `using namespace std;`
11. `const int N = 200 + 10;`
12. `vector<int> g[N];`
13. `int cy[N];`
14. `bool vis[N];`
15. `bool dfs(int u)`
16. `{`
17. `for(int i=0; i<g[u].size(); ++i)`
18. `{`
19. `int v = g[u][i];`
20. `if(vis[v]) continue;`
21. `vis[v] = true;`
22. `if(cy[v]==-1 || dfs(cy[v])){`
23. `cy[v] = u;`
24. `return true;`
25. `}`
26. `}`
27. `return false;`
28. `}`
29. `int solve(int n)`
30. `{`
31. `int ret = 0;`
32. `memset(cy, -1, sizeof(cy));`
33. `for(int i=1;i<=n;++i)`
34. `{`
35. `memset(vis, 0, sizeof(vis));`
36. `ret += dfs(i);`
37. `}`
38. `return n - ret;`
39. `}`
40. `int main( )`
41. `{`
42. `int t,n,m;`
43. `int u,v;`
44. `scanf("%d",&t);`
45. `while(t--)`
46. `{`
47. `scanf("%d%d",&n,&m);`
48. `for(int i=1;i<=n;++i)`
49. `g[i].clear();`
50. `for(int i=0;i<m;++i)`
51. `{`
52. `scanf("%d%d",&u,&v);`
53. `g[u].push_back(v);`
54. `}`
55.  
56. `int ans = solve(n);`
57. `printf("%d\n",ans);`
58. `}`
59. `return 0;`
60. `}`

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

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

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

上面的解释很不错，点个赞！

**题目**：[POJ2594][]

1.  `//`
2.  `// main.cpp`
3.  `// POJ2594最小可相交路径覆盖`
4.  `//`
5.  `// Created by beMaster on 16/4/8.`
6.  `// Copyright © 2016年 beMaster. All rights reserved.`
7.  `//`
8.   
9.  `#include <iostream>`
10. `#include <stdio.h>`
11. `#include <string.h>`
12. `#include <vector>`
13. `using namespace std;`
14. `const int N = 500 + 10;`
15. `bool dis[N][N];`
16. `bool vis[N];`
17. `int cy[N];`
18. `void floyd(int n){`
19. `for(int i=1;i<=n;++i)`
20. `for(int j=1;j<=n;++j)`
21. `for(int k=1;k<=n;++k)`
22. `if(dis[i][k] && dis[k][j])//传递可达性`
23. `dis[i][j] = true;`
24. `}`
25. `bool dfs(int u, int n){`
26. `for(int i=1;i<=n;++i){`
27. `if(!vis[i] && dis[u][i]){`
28. `vis[i] = true;`
29. `if(cy[i]==-1 || dfs(cy[i], n)){`
30. `cy[i] = u;`
31. `return true;`
32. `}`
33. `}`
34. `}`
35. `return false;`
36. `}`
37. `int solve(int n){`
38. `int cnt = 0;`
39. `memset(cy,-1,sizeof(cy));`
40. `for(int i=1;i<=n;++i){`
41. `memset(vis,0,sizeof(vis));`
42. `cnt += dfs(i, n);`
43. `}`
44. `return n - cnt;`
45. `}`
46. `int main( ) {`
47. `int n,m;`
48. `int a,b;`
49. `while(scanf("%d%d",&n,&m),n+m){`
50. `for(int i=1;i<=n;++i)`
51. `for(int j=1;j<=n;++j)`
52. `dis[i][j] = false;`
53. `for(int i=1;i<=m;++i){`
54. `scanf("%d%d",&a,&b);`
55. `dis[a][b] = true;`
56. `}`
57. `floyd(n);`
58. `int ans = solve(n);`
59. `printf("%d\n",ans);`
60. `}`
61. `return 0;`
62. `}`

做完这两道例题，可以做做我拉的题目啊，欢迎欢迎

[https://vjudge.net/contest/249592\#problem][https_vjudge.net_contest_249592_problem]

[https_blog.csdn.net_qq_39627843_article_details_82012572]: https://blog.csdn.net/qq_39627843/article/details/82012572
[70]: /images/20220121/89c8c7168bbb4018b392d544416d1a85.png
[https_blog.csdn.net_Arabic1666_article_details_79824390]: https://blog.csdn.net/Arabic1666/article/details/79824390
[POJ1422]: http://poj.org/problem?id=1422
[POJ2594]: http://poj.org/problem?id=2594
[https_vjudge.net_contest_249592_problem]: https://vjudge.net/contest/249592#problem