【网络流24题】 No.3 最小路径覆盖问题（网络流|匈牙利算法 ->最大二分匹配）

【题意】

　　给定有向图 G=(V,E)。设 P 是 G 的一个简单路（顶点不相交）的集合。如果 V 中每个
顶点恰好在 P 的一条路上，则称 P 是 G 的一个路径覆盖。 P 中路径可以从 V 的任何一个顶
点开始，长度也是任意的，特别地，可以为 0。 G 的最小路径覆盖是 G 的所含路径条数最少
的路径覆盖。
设计一个有效算法求一个有向无环图 G 的最小路径覆盖。

输入文件示例
input.txt
11 12
1 2
1 3
1 4
2 5
3 6
4 7
5 8
6 9
7 10
8 11
9 11
10 11

输出文件示例
output.txt
1 4 7 10 11
2 5 8
3 6 9
3

【分析】

　　假设一开始每个点是一条路径，如果有一条有向边u->v 那么可以减少一条路径，但选这些有向边集合每个点的入度出度都为1.

　　那就是一个最大二分匹配。

　　这次我打的是网络流哦~

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<iostream>
  5 #include<algorithm>
  6 #include<queue>
  7 using namespace std;
  8 #define Maxn 1100
  9 #define INF 0xfffffff
 10 
 11 struct node
 12 {
 13     int x,y,f,o,next;
 14 }t[Maxn*Maxn];int len;
 15 int first[Maxn];
 16 
 17 int mymin(int x,int y) {return x<y?x:y;}
 18 
 19 void ins(int x,int y,int f)
 20 {
 21     t[++len].x=x;t[len].y=y;t[len].f=f;
 22     t[len].next=first[x];first[x]=len;t[len].o=len+1;
 23     t[++len].x=y;t[len].y=x;t[len].f=0;
 24     t[len].next=first[y];first[y]=len;t[len].o=len-1;
 25 }
 26 
 27 int st,ed;
 28 queue<int > q;
 29 int dis[Maxn];
 30 bool bfs()
 31 {
 32     while(!q.empty()) q.pop();
 33     memset(dis,-1,sizeof(dis));
 34     q.push(st);dis[st]=0;
 35     while(!q.empty())
 36     {
 37         int x=q.front();
 38         for(int i=first[x];i;i=t[i].next) if(t[i].f>0)
 39         {
 40             int y=t[i].y;
 41             if(dis[y]==-1)
 42             {
 43                 dis[y]=dis[x]+1;
 44                 q.push(y);
 45             }
 46         }
 47         q.pop();
 48     }
 49     if(dis[ed]==-1) return 0;
 50     return 1;
 51 }
 52 
 53 int ffind(int x,int flow)
 54 {
 55     if(x==ed) return flow;
 56     int now=0;
 57     for(int i=first[x];i;i=t[i].next) if(t[i].f>0)
 58     {
 59         int y=t[i].y;
 60         if(dis[y]==dis[x]+1)
 61         {
 62             int a=ffind(y,mymin(flow-now,t[i].f));
 63             t[i].f-=a;
 64             t[t[i].o].f+=a;
 65             now+=a;
 66         }
 67         if(now==flow) break;
 68     }
 69     if(now==0) dis[x]=-1;
 70     return now;
 71 }
 72 
 73 void output()
 74 {
 75     for(int i=1;i<=len;i+=2)
 76      printf("%d->%d %d
",t[i].x,t[i].y,t[i].f);
 77 }
 78 
 79 int max_flow()
 80 {
 81     int ans=0;
 82     while(bfs())
 83     {
 84         ans+=ffind(st,INF);
 85         // printf("--%d
",ans);
 86         // output();
 87     }
 88     return ans;
 89 }
 90 
 91 int nt[Maxn];
 92 bool qq[Maxn];
 93 
 94 int main()
 95 {
 96     int n,m;
 97     scanf("%d%d",&n,&m);
 98     len=0;
 99     memset(first,0,sizeof(first));
100     for(int i=1;i<=m;i++)
101     {
102         int x,y;
103         scanf("%d%d",&x,&y);
104         ins(x,y+n,1);
105     }
106     st=2*n+1;ed=st+1;
107     for(int i=1;i<=n;i++) ins(st,i,1);
108     for(int i=1;i<=n;i++) ins(i+n,ed,1);
109     memset(nt,0,sizeof(nt));
110     memset(qq,1,sizeof(qq));
111     int x=max_flow();
112     // output();
113     for(int i=1;i<=len;i+=2) if(t[i].x!=st&&t[i].y!=ed&&t[i].f==0)
114         nt[t[i].x]=t[i].y-n,qq[t[i].y-n]=0;
115     for(int i=1;i<=n;i++) if(qq[i])
116     {
117         int x=i;
118         while(x)
119         {
120             printf("%d ",x);
121             x=nt[x];
122         }printf("
");
123     }
124     printf("%d
",n-x);
125     return 0;
126 }

View Code

2016-11-04 10:13:40

【网络流24题】 No.3 最小路径覆盖问题 （网络流|匈牙利算法 ->最大二分匹配）

【网络流24题】 No.3 最小路径覆盖问题（网络流|匈牙利算法 ->最大二分匹配）