【网络流24题】最小路径覆盖问题

2023-11-18 15:08:34

题目描述

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

提示：设 V=\{1,2,...,n\}V={1,2,...,n} ，构造网络 G_1=\{V_1,E_1\}G1={V1,E1} 如下：

V_1=\{x_0,x_1,...,x_n\}\cup\{y_0,y_1,...,y_n\}V1={x0,x1,...,xn}∪{y0,y1,...,yn}

E_1=\{(x_0,x_i):i\in V\}\cup\{(y_i,y_0):i\in V\}\cup\{(x_i,y_j):(i,j)\in E\}E1={(x0,xi):i∈V}∪{(yi,y0):i∈V}∪{(xi,yj):(i,j)∈E}

每条边的容量均为 11 ，求网络 G_1G1 的 (x_0,y_0)(x0,y0) 最大流。

输入输出格式

输入格式：

第一行有 22 个正整数 nn 和 mm 。 nn 是给定\text{GAP}GAP(有向无环图) GG 的顶点数， mm 是 GG 的边数。接下来的 mm 行,每行有两个正整数 ii 和 jj 表示一条有向边 (i,j)(i,j)。

输出格式：

从第1 行开始，每行输出一条路径。文件的最后一行是最少路径数。

输入输出样例

输入样例#1：复制

输出样例#1：复制

1 4 7 10 11
2 5 8
3 6 9
3

说明

1\leq n\leq 150,1\leq m\leq 60001≤n≤150,1≤m≤6000

由@FlierKing提供SPJ

这题目描述里都写明白了。。。

但是拿方案那里写的出了几次错，需要格外注意下

 1 #include<bits/stdc++.h>
 2 #define N 505
 3 #define M 100000
 4 #define INF (1<<30)
 5 using namespace std;
 6 int n,m;
 7 int h[N],to[M],nxt[M],fl[M],etop;
 8 int nex[N];
 9 int S=0,T=500;
10 void add(int u,int v,int w){
11     to[etop]=v,nxt[etop]=h[u],fl[etop]=w,h[u]=etop++;
12     to[etop]=u,nxt[etop]=h[v],fl[etop]=0,h[v]=etop++;
13 }
14 int lev[N];
15 queue<int>q;
16 inline bool bfs(){
17     memset(lev,-1,sizeof(lev));
18     lev[S]=0;
19     q.push(S);
20     while(!q.empty()){
21         int u=q.front();q.pop();
22         for(int k=h[u];~k;k=nxt[k]){
23             int v=to[k];
24             if(fl[k]&&lev[v]==-1){
25                 lev[v]=lev[u]+1;
26                 q.push(v);
27             }
28         }
29     }
30     return lev[T]!=-1;
31 }
32 inline int dfs(int u,int t,int left){
33     if(u==t)return left;
34     for(int k=h[u];~k;k=nxt[k]){
35         int v=to[k];
36         if(lev[v]==lev[u]+1&&fl[k]){
37             int d=dfs(v,t,min(left,fl[k]));
38             if(d){
39                 fl[k]-=d;
40                 fl[k^1]+=d;
41                 if(v!=T)nex[u]=v;
42                 return d;
43             }
44         }
45     }
46     return 0;
47 }
48 int dinic(){
49     int flow=0,f;
50     while(bfs()){
51         while(f=dfs(S,T,INF))flow+=f;
52     }
53     return flow;
54 }
55 int in[N];
56 int main(){
57     //freopen("testdata.in","r",stdin);
58     //freopen("my.out","w",stdout);
59     scanf("%d%d",&n,&m);
60     memset(h,-1,sizeof(h));
61     memset(nex,-1,sizeof(nex));
62     for(int i=1,u,v;i<=m;i++){
63         scanf("%d%d",&u,&v);
64         add(u<<1,v<<1|1,1);
65     }
66     for(int i=1;i<=n;i++)add(S,i<<1,1),add(i<<1|1,T,1);
67     int ans=dinic();
68     for(int i=1;i<=n;i++)
69     if(nex[i<<1]!=-1)in[nex[i<<1]>>1]++;
70     for(int i=1;i<=n;i++)
71     if(in[i]==0)q.push(i);
72     while(!q.empty()){
73         int u=q.front();q.pop();
74         cout<<u;u=nex[u<<1]>>1;
75         while(u!=-1){
76             cout<<' '<<u;
77             u=nex[u<<1]>>1;
78         }
79         cout<<endl;
80     }
81     cout<<n-ans<<endl;
82     return 0;    
83 }
84 /*
85 4 4
86 4 2
87 1 3
88 2 3
89 4 3
90 */

View Code

码农公寓

题目描述

输入输出格式

输入输出样例

说明

相关文章