[转载]网络流四·最小路径覆盖

啊哈磊

转载自：https://blog.csdn.net/tramp_1/article/details/52742572网络流四·最小路径覆盖

H市一共有N个旅游景点(编号1..N)，由M条单向游览路线连接。在一个景点游览完后，可以顺着游览线路前往下一个景点。

为了避免游客重复游览同一个景点，游览线路保证是没有环路的。

每一个调查团可以从任意一个景点出发，沿着计划好的游览线路依次调查，到达终点后再返回。每个景点只会有一个调查团经过，不会重复调查。

举个例子：

上图中一共派出了3个调查团：

1. 蓝色：调查景点；2

2. 橙色：调查景点；1->3->4->6

3. 绿色：调查景点；5->7

当然对于这个图还有其他的规划方式，但是最少也需要3个调查团。

由于小组内的人数有限，所以大家希望调查团的数量尽可能少，同时也要将所有的景点都进行调查。

输入

第1行：2个整数N,M。1≤N≤500,0≤M≤20,000。

第2..M+1行：2个数字u,v，表示一条有向边(u,v)。保证不会出现重复的边，且不存在环。

输出

第1行：1个整数，表示最少需要的调查团数量。

样例输入7 71 21 32 43 44 54 65 7样例输出3


提示：最小路径覆盖

对于一条路径，起点的入度为0，终点的出度为0，中间节点的出入度都为1。

每一个点最多只能有1个后继，同时每一个点最多只能有1个前驱。

假如我们选择了一条边(u,v)，也就等价于把前驱u和后继v匹配上了。这样前驱u和后继v就不能和其他节点匹配。

利用这个我们可以这样来构图：

将每一个点拆分成2个，分别表示它作为前驱节点和后继节点。将所有的前驱节点作为A部，所有后继节点作为B部。

接下来进行连边，若原图中存在一条边(u,v)，则连接A部的u和B部的v。

在这个上面做一个最大二分匹配：

其中实线表示被选中的匹配，虚线表示未被选中的。

有没有发现，和原图刚好有着对应的关系。

这样在匹配结束的时候，我们就可以直接通过匹配的情况来确定选中的路径。

但是如何保证这样就能得到最小的路径覆盖呢？

如果一个点是路径起点的话，它在B部的节点一定是没有匹配上的。

经过最大匹配算法后，B部剩下没有被匹配的点一定是最少的，也就对应了最小需要的路径数。

所以最小路径覆盖的结果才是N-最大匹配数。

正是这样，这样问题也就解决了。接下来第二个问题，怎么用网络流来解决二分匹配呢？

上一次我们讲了二分多重匹配，二分匹配不就是它的简化版么。

只需要把源点s到A部的边和B部到汇点t的边容量限定为1就可以了！

1. #include <iostream>
   
2. #include <cstdio>
   
3. #include <cstdlib>
   
4. #include <cstring>
   
5. #include <algorithm>
   
6. #define MAX 1010
   
7. #define MAXCF 101
   
8. #define min(a,b) (a)>(b)?(b):(a)
   
9. using namespace std;
   
10. 
    
11. int cf[MAX][MAX];//存储图
    
12. int queue[MAX];//搜索队列
    
13. int path[MAX];//保存路径
    
14. int capacity[MAX];//流量数组，保存经过该点的最小流量
    
15. bool visited[MAX];//记录访问数组
    
16. 
    
17. int findAugmentPath(int T)
    
18. {
    
19.         int i = 0, tail = 0;
    
20.         memset(visited, 0, sizeof(visited));
    
21. 
    
22.         queue[tail] = 1;//将源点加入队列
    
23.         capacity[1] = MAXCF;
    
24.         visited[1] = true;
    
25.         while (i <= tail)
    
26.         {
    
27.                 int u = queue[i];
    
28.                 if (u == T)
    
29.                         return capacity[T];//找到一条增广路径，返回该路径最小流量
    
30.                 for (int v = 2; v <= T; v++)
    
31.                 {
    
32.                         if (!visited[v] && cf[u][v] > 0)
    
33.                         {
    
34.                                 path[v] = u;
    
35.                                 capacity[v] = min(cf[u][v], capacity[u]);//记录路径上的最小残余流量
    
36.                                 visited[v] = true;
    
37.                                 tail++;
    
38.                                 queue[tail] = v;
    
39.                         }
    
40.                 }
    
41.                 i++;
    
42.         }
    
43.         return 0;
    
44. }
    
45. 
    
46. void modifyGraph(int T)
    
47. {
    
48.         int flow = capacity[T];
    
49.         int now = T;
    
50.         while (now != 1)
    
51.         {
    
52.                 int fa = path[now];
    
53.                 cf[fa][now] -= flow;
    
54.                 cf[now][fa] += flow;
    
55.                 now = fa;
    
56.         }
    
57. }
    
58. 
    
59. int main()
    
60. {
    
61.         int N, M;
    
62.         int i, j;
    
63.         int u, v;
    
64. 
    
65.         while (cin >> N >> M)
    
66.         {
    
67.                 int S = 1;
    
68.                 int E = S + N + N + 1;
    
69.                 int result = 0;
    
70.                 memset(cf, 0, sizeof(cf));
    
71.                 for (i = 0; i < N; ++i)
    
72.                 {
    
73.                         cf[S][S + i + 1] = 1;
    
74.                         cf[S + N + i + 1][E] = 1;
    
75.                 }
    
76.                 for (i = 0; i < M; ++i)
    
77.                 {
    
78.                         cin >> u >> v;
    
79.                         cf[S + u][S + N + v] = 1;
    
80.                 }
    
81. 
    
82.                 int maxFlow = 0;
    
83.                 int delta = 0;
    
84.                 while (delta = findAugmentPath(E))
    
85.                 {
    
86.                         maxFlow += delta;
    
87.                         modifyGraph(E);
    
88.                 }
    
89.                 cout << N - maxFlow << endl;
    
90.                
    
91.         }
    
92.         return 0;
    
93. }

复制代码

创世菌

That looks quite useful!

朱艳

纪总，你好，新浪微博官方代理商，主要是通过微博，帮你们做强曝光和客资，目前编程猫，在微博投放，客资成本100-150，方便的话，具体沟通下，看有没有合作机会。。。。朱艳15005184827手机号同微信号