Criska

网络流

• 分类: 网络流 • 标签: 网络流

向网络流24题进军……

先放一个模板题o(︶︿︶)o

【模板】网络最大流

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int N=500050;
const int p=0x7fffffff;
int n,m,s,t,tope=0,ans=0;
queue<int>q;
int head[N],ds[N];
struct node{
	int to,next,w;
}e[N];
inline int intt(int x,int y,int z)
{
	tope++;
	e[tope].to=y;
	e[tope].next=head[x];
	e[tope].w=z;
	head[x]=tope;
	tope++;
	e[tope].to=x;
	e[tope].next=head[y];
	e[tope].w=0;
	head[y]=tope;
}
inline int bfs()
{
	for(int i=1;i<=m;++i) ds[i]=-1;
	q.push(s);ds[s]=0;
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		for(int i=head[x];i;i=e[i].next)
		{
			int y=e[i].to;
			if(e[i].w&&ds[y]==-1)
			{
				ds[y]=ds[x]+1;
				q.push(y);
			}
		}
	}
	return ds[t]>-1;
	
}
inline int dfs(int x,int f)
{
	if(x==t) return f;
	int a=0,b;
	for(int i=head[x];i;i=e[i].next)
	{
		int y=e[i].to;
		if(e[i].w&&ds[y]==ds[x]+1)
		{
			b=dfs(y,min(f-a,e[i].w));
			e[i].w-=b;
			if(i%2) e[i+1].w+=b;
			else e[i-1].w+=b;
			a+=b;
			if(a==f) break;
			
		}
	}
	if(a==0) ds[x]=-1;
	return a;
}
int main()
{
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for(int i=1;i<=m;++i)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		intt(x,y,z);
	}
	while(bfs()) ans+=dfs(s,p);
	printf("%d",ans);
	return 0;
}

最大流

1.搭配飞行员

二分图最大匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<iostream>
#include<cstdio>
#include<queue>
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int N=500050;
const int p=2147483646;
int m,n,tope=0,tot=0;
int head[N],ds[N],pr[N],su[N];
int ans=0;
queue<int>q;
struct node{
	int to,next,w;
}e[N];
inline int intt(int x,int y,int z)
{
	tope++;
	e[tope].next=head[x];
	e[tope].w=z;
	e[tope].to=y;
	head[x]=tope;
	tope++;
	e[tope].next=head[y];
	e[tope].w=0;
	e[tope].to=x;
	head[y]=tope;
}
inline int bfs()
{
	for(int i=0;i<=n+2;++i) ds[i]=-1;
	q.push(1);ds[1]=0;
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		for(int i=head[x];i;i=e[i].next)
		{
			int y=e[i].to;
			if(e[i].w&&ds[y]==-1)
			{
				ds[y]=ds[x]+1;
				q.push(y);
			}
		}
	}
	return ds[n+2]>0;
}
inline int dfs(int x,int f)
{
	if(x==n+2) return f;
	int a=0,b;
	for(int i=head[x];i;i=e[i].next)
	{
		int y=e[i].to;
		if(e[i].w&&ds[y]==ds[x]+1)
		{
			b=dfs(y,min(f-a,e[i].w));
			e[i].w-=b;
			if(i%2) e[i+1].w+=b;
			else e[i+1].w+=b;
			a+=b;
			if(x!=1&&y!=n+2)
			{
				pr[++tot]=x;
				su[tot]=y;
			}
			if(a==f) break;
		}
	}
	if(a==0) ds[x]=-1;
	return a;
}
int main()
{
	freopen("flyer.in","r",stdin);
	freopen("flyer.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=2;i<=m+1;++i) intt(1,i,1);
	for(int i=m+2;i<=n+1;++i) intt(i,n+2,1); 
	int u,v;
	while(scanf("%d%d",&u,&v)!=EOF) 
	intt(u+1,v+1,1);
	while(bfs()) ans+=dfs(1,p);
	printf("%d\n",ans);	
	return 0;
}

2.圆桌聚餐

输出方案的二分图最大匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int N=100000;
const int p=2147483640;
int m,n,tope=0,s,t,ans=0,sum=0,tot=0,r[N];
int head[N],ds[N];
queue<int>q;
struct node{
	int to,next,w;
}e[N];
int intt(int x,int y,int z)
{
	tope++;
	e[tope].to=y;
	e[tope].next=head[x];
	e[tope].w=z;
	head[x]=tope;
	tope++;
	e[tope].to=x;
	e[tope].next=head[y];
	e[tope].w=0;
	head[y]=tope;
}
inline int bfs()
{
	for(int i=0;i<=t;++i) ds[i]=-1;
	q.push(s);ds[s]=0;
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		for(int i=head[x];i;i=e[i].next)
		{
			int y=e[i].to;
			if(e[i].w&&ds[y]==-1)
			{
				ds[y]=ds[x]+1;
				q.push(y);
			}
		}
	}
	return ds[t]>0;
}
inline int dfs(int x,int f)
{
	if(x==t) return f;
	int a=0,b;
	for(int i=head[x];i;i=e[i].next)
	{
		int y=e[i].to;
		if(e[i].w&&ds[y]==ds[x]+1)
		{
			b=dfs(y,min(e[i].w,f-a));
			e[i].w-=b;
			if(i%2) e[i+1].w+=b;
			else e[i-1].w+=b;
			a+=b;
			if(a==f) break;
		} 
	}
	if(a==0) ds[x]=-1;
	return a;
}
int main()
{
	freopen("roundtable.in","r",stdin);
	freopen("roundtable.out","w",stdout);
	scanf("%d%d",&m,&n);
	s=1;t=m+n+2;
	for(int i=2;i<=m+1;++i)
	{
		int x;
		scanf("%d",&x);
		intt(1,i,x);
		sum+=x;
	}
	for(int i=m+2;i<=m+1+n;++i)
	{
		int x;
		scanf("%d",&x);
		for(int j=2;j<=m+1;++j)
		{
			intt(j,i,1);
		}
		intt(i,t,x);
	}
	while(bfs()) ans+=dfs(1,p);
	if(sum==ans)
	{
		printf("1\n");
		for(int x=2;x<=m+1;++x)
		{
			for(int i=1;i<=tot;++i) r[i]=0;
			tot=0;
			for(int i=head[x];i;i=e[i].next)
			{
				if(e[i].w==0&&e[i].to!=1) r[++tot]=e[i].to-m-1;
			}
			sort(r+0,r+tot+1);
			for(int i=1;i<=tot;++i)
			{
				printf("%d ",r[i]);
			}
			printf("\n");
		}
	}
	else printf("0");
	return 0;
}

3.试题库

和圆桌聚餐基本一样= =

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
 #include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
const int N=100010;
const int p=2147483646;
using namespace std;
int tope=0,n,m,s,t,k,ans=0,sum=0,tot=0;
int head[N],ds[N],r[N];
queue<int>q;
struct node{
	int to,next,w;
}e[N];
inline int intt(int x,int y,int z)
{
	tope++;
	e[tope].to=y;
	e[tope].w=z;
	e[tope].next=head[x];
	head[x]=tope;
	tope++;
	e[tope].to=x;
	e[tope].w=0;
	e[tope].next=head[y];
	head[y]=tope;
}
inline int bfs()
{
	for(int i=0;i<=t;++i) ds[i]=-1;
	q.push(s); ds[s]=0;
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		for(int i=head[x];i;i=e[i].next)
		{
			int y=e[i].to;
			if(e[i].w&&ds[y]==-1)
			{
				ds[y]=ds[x]+1;
				q.push(y);
			}
		}
	}
	return ds[t]>0;
}
inline int dfs(int x,int f)
{
	if(x==t) return f;
	int a=0,b;
	for(int i=head[x];i;i=e[i].next)
	{
		int y=e[i].to;
		if(e[i].w&&ds[y]==ds[x]+1)
		{
			b=dfs(y,min(e[i].w,f-a));
			e[i].w-=b;
			if(i%2) e[i+1].w+=b;
			else e[i-1].w+=b;
			a+=b;
			if(a==f) break;
		}
	}
	if(a==0) ds[x]=-1;
	return a;
}
int main()
{
	freopen("testlib.in","r",stdin);
	freopen("testlib.out","w",stdout);
	scanf("%d%d",&k,&n);
	s=1;t=k+n+2;
	for(int i=2;i<=k+1;++i)
	{
		int x;
		scanf("%d",&x); 
		intt(i,t,x);
		sum+=x;
	}
	for(int i=k+2;i<=t-1;++i)
	{
		int x,y;
		scanf("%d",&x);
		for(int j=1;j<=x;++j)
		{
			scanf("%d",&y);
			intt(i,y+1,1);
		}
		intt(1,i,1);
	}
	while(bfs()) ans+=dfs(s,p);
	if(ans==sum)
	{
		for(int x=2;x<=k+1;++x)
		{
			for(int i=1;i<=tot;++i) r[i]=0;
			tot=0;
			for(int i=head[x];i;i=e[i].next)
			{
				int y=e[i].to;
				if(y!=t&&e[i].w)
				{
					r[++tot]=y-k-1;
				}
			}
			sort(r+0,r+tot+1);
			for(int i=1;i<=tot;++i)
			printf("%d ",r[i]);
			printf("\n");
		}
	}
	else
	{
		printf("NoSolution!");
	}
	return 0;
}

4.最小路径覆盖问题

这是一道神奇的题，因为题目已经告诉你题解了= =
来自黄学长的真实题解：

将每个点都分别放入xy集合中
如果u到v有一条边,则x集合的u向y集合的v连一条权值inf的边
S向x集合的点连边，权值1，y集合的点向T连边，权值1，做一遍最大流，得出最大匹配数
ans=n-最大匹配
如果无匹配，显然要n条路径才能覆盖所有点，两个点匹配意味着将可以把它们用一条路径覆盖，路径数就可以减1

最小路径覆盖问题怎么转化成最大流问题呢？（来自网络ww）

上图中,对应左边的DAG建立构造右边的二分图,可以找到二分图的一个最大匹配M:1-3’,3-4’,那么M中的这两条匹配边怎样对应DAG中的路径的边?
使二分图中一条边对应DAG中的一条有向边,1-3’对应DAG图中的有向边1->3,这样DAG中1就会有一个后继顶点(3会是1的唯一后继,因为二分图中一个顶点至多关联一条边!),所以1不会成为DAG中一条路径中的结尾顶点,同样,3-4’对应DAG中3->4,3也不会成为结尾顶点,那么原图中总共4个顶点,减去2个有后继的顶点,就剩下没有后继的顶点,即DAG路径的结尾顶点,而每个结尾顶点正好对应DAG中的一条路径,二分图中寻找最大匹配M,就是找到了对应DAG中的非路径结尾顶点的最大数目,那么DAG中顶点数-|M|就是DAG中结尾顶点的最小数目,即DAG的最小路径覆盖数.即上图中找到的最小路径覆盖集合为2， 1->3->4。

咦这么说来我好像少判断了一种情况，不过A了……= =
最后一行不输出换行会WA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int N=100010;
const int p=2147483646;
int n,m,tope=0,ans=0,s,t;
int head[N],ds[N],u[N];
queue<int>q;
struct node{
	int to,next,w;
}e[N];
inline int intt(int x,int y,int z)
{
	tope++;
	e[tope].to=y;
	e[tope].next=head[x];
	e[tope].w=z;
	head[x]=tope;
	tope++;
	e[tope].to=x;
	e[tope].next=head[y];
	e[tope].w=0;
	head[y]=tope;
}
inline int bfs()
{
	for(int i=1;i<=t;++i) ds[i]=-1;
	q.push(s); ds[s]=0;
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		for(int i=head[x];i;i=e[i].next)
		{
			int y=e[i].to;
			if(e[i].w&&ds[y]==-1)
			{
				ds[y]=ds[x]+1;
				q.push(y);
			}
		}
	}
	return ds[t]>0;
}
inline int dfs(int x,int f)
{
	if(x==t) return f;
	int a=0,b;
	for(int i=head[x];i;i=e[i].next)
	{
		int y=e[i].to;
		if(e[i].w&&ds[y]==ds[x]+1)
		{
			b=dfs(y,min(e[i].w,f-a));
			a+=b;
			e[i].w-=b;
			if(i%2) e[i+1].w+=b;
			else e[i-1].w+=b;
			if(a==f) break;
		}
	}
	if(a==0) ds[x]=-1;
	return a;	
}
inline int sou(int x)
{
	for(int i=head[x];i;i=e[i].next)
	{
		int y=e[i].to;
		if(u[y-n]==0&&y!=s&&e[i].w==0)
		{
			printf("%d ",y-n);
			u[y-n]=1;
			sou(y-n);
		}
	}
}
int main()
{
	freopen("path3.in","r",stdin);
	freopen("path3.out","w",stdout);
	scanf("%d%d",&n,&m);
	s=1+2*n;t=2+2*n;
	for(int i=1;i<=m;++i)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		intt(x,y+n,1);
	}
	for(int i=1;i<=n;++i)
	{
		intt(s,i,1);
		intt(i+n,t,1);
	}
	while(bfs()) ans+=dfs(s,p);
	for(int x=1;x<=n;++x)
	{
		if(u[x]==0)
		{
			printf("%d ",x);
			u[x]=1;
			sou(x);
			printf("\n");
		}
	}
	printf("%d\n",n-ans);
	return 0;
}