Tang-Dreamoon's Blog

Poj 1895 分层网络流

发表于 | 分类于 ， ，

动态加层，动态加点

　　题目链接：poj 1895

　　题意：在公元3141年人类的足迹已经遍布银河系。为了穿越那巨大的距离，人类发明了一种名为超时空隧道的技术。超时空隧道是双向的，连接两个星系，穿越一次需要一天的时间。然而这个轨道只能同时给一艘飞船使用，也就是说，每条隧道每天只能有一艘飞船穿越。现在 I B M 公司要把 K 艘飞船从 S 运送到 T 。现在人类能够到达 N 个星系，拥有 M 条超时空隧道，请问至少需要几天才能将这些飞船开到目的地。

　　题解：感觉这个题非常的难，真心很难很恶心。首先从小到大枚举答案 a n s ，构造（a n s + 1）层的图，每层都是原图的 N 个点。源点连第一层的 S ，容量为 K ；所有层的 T 连向汇点，容量为 ﹢ ∞ 。对于原图中的无向边（U，V），从上一层的 U 、V 连向下一层 V 、U ，容量为 1 表示每天只能有一艘飞船飞过。那暂且停滞不能前行的飞船怎么办呢？我们再对于图中的每一个点 i 都向下一层的点 i 连边，容量为﹢ ∞，表示今天没有前行。求最大流，如果最大流等于 K ，那么我们当前枚举的 a n s 就是答案。不过这个题最难的显然是输出方案：从原点出发 D f s K次，得到 K 条路径。每次 D f s 时寻找一条从当前点出发有流的边走过去，并且把这条边的流减一，直到到达汇点。

　　我思故我在：通过这一道题我真的学会了如何动态加层，因为这一道题显然不能每次将图清空重新跑网络流，所以我们需要动态加层，每次再增广新的流量然后累计到原来的答案上。除此之外，在搜索方案的时候还要注意以下几点：如果从当前层的 i 走到了下一层的 i ，实际上是没有动的，因此这条边不能记录到方案里。如果相邻两层之间的（U，V）和（V，U）都有流，根据题目要求，一条路上不能有两个不同方向的流同时流过。但是这样的方案可以等效成两个流各自停留在 U 和 V 没有移动，而在后边的路程中两个流的路径进行了交换。

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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int n,m,k,s,t;
int ss,tt;
int tot=0;
struct table{
	int to,id;
};
vector<table> ve[50500];
vector<int> va[50500];
struct node{
	int l,r;
}map[233];
int f[505000];
int deep[50500];
int now[5051][5051];
inline int min(int a,int b)
{
	return a < b ? a : b ;
}
inline bool bfs()
{
	memset(deep,-1,sizeof(deep));
	queue<int> q;
	deep[ss]=0;
	q.push(ss);
	while(!q.empty())
	{
		int x=q.front();q.pop();
		for(int i=0;i<ve[x].size();i++)
		{
			table y=ve[x][i];
			if(deep[y.to]==-1&&f[y.id]>0)
			{
				deep[y.to]=deep[x]+1;
				q.push(y.to);
			}
		}
	}
	return deep[tt]!=-1;
}
inline int zeng(int a,int b)
{
	if(a==tt) return b;
	int r=0,t;
	for(int i=0;i<ve[a].size();i++)
	{
		table y=ve[a][i];
		if(deep[y.to]==deep[a]+1&&f[y.id]>0)
		{
			t=zeng(y.to,min(b-r,f[y.id]));
			r+=t,f[y.id]-=t,f[y.id^1]+=t;
		}
	}
	if(!r) deep[a]=-1;
	return r;
}
inline int dinic()
{
	int ans=0,now;
	while(bfs())
	{
		while(now=zeng(ss,247483647)) ans+=now;
	}
	return ans;
}
void dfs(int num,int x,int love,int ceng)
{
	if(x-ceng*n==t) return ;
	for(int i=0;i<ve[x].size();i++)
	{
		table y=ve[x][i];
		if(f[y.id]!=1&&f[y.id]!=247483647&&(y.id%2==0))
		{
			f[y.id]++;
			if(y.to==x+n)
			{
				dfs(num,y.to,love,ceng+1);
				return ;
			}
			else
			{
				if(f[now[y.to-n][x+n]]==0)
				{
					f[now[y.to-n][x+n]]++;
					f[now[y.to-n][y.to]]--;
					dfs(num,x+n,love,ceng+1);
					return ;
				}
				else
				{
					va[ceng].push_back(num);
					va[ceng].push_back(y.to-ceng*n);
					dfs(num,y.to,love,ceng+1);
					return ;
				}
			}
		}
	}
}
int main()
{
	scanf("%d%d%d%d%d",&n,&m,&k,&s,&t);
	ss=4999,tt=5000;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		map[i].l=x,map[i].r=y;
	}
	int ans=1;
	int sum=n;
	now[ss][s]=tot;
	ve[ss].push_back((table){s,tot}),f[tot++]=k;
	ve[s].push_back((table){ss,tot}),f[tot++]=0;
	for(int i=1;i<=n;i++)
	{
		now[i][i+n]=tot;
		ve[i].push_back((table){i+n,tot}),f[tot++]=247483647;
		ve[i+n].push_back((table){i,tot}),f[tot++]=0;
	}
	for(int i=1;i<=m;i++)
	{
		int x=map[i].l,y=map[i].r;
		now[x][y+n]=tot;
		ve[x].push_back((table){y+n,tot}),f[tot++]=1;
		ve[y+n].push_back((table){x,tot}),f[tot++]=0;
		now[y][x+n]=tot;
		ve[y].push_back((table){x+n,tot}),f[tot++]=1;
		ve[x+n].push_back((table){y,tot}),f[tot++]=0;
	}
	now[t+n][tt]=tot;
	ve[t+n].push_back((table){tt,tot}),f[tot++]=247483647;
	ve[tt].push_back((table){t+n,tot}),f[tot++]=0;
	int p=0;
	while(2333)
	{
		p+=dinic();
	    if(p==k) break;
//		for(int i=0;i<tot;i+=2)
//		{
//			f[i]+=f[i^1];
//		    f[i^1]=0;
//		}
		for(int i=1;i<=n;i++)
		{
			now[i+sum][i+sum+n]=tot;
			ve[i+sum].push_back((table){i+sum+n,tot}),f[tot++]=247483647;
			ve[i+sum+n].push_back((table){i+sum,tot}),f[tot++]=0;
		}
		for(int i=1;i<=m;i++)
		{
			int x=map[i].l,y=map[i].r;
			now[x+sum][y+sum+n]=tot;
			ve[x+sum].push_back((table){y+sum+n,tot}),f[tot++]=1;
			ve[y+sum+n].push_back((table){x+sum,tot}),f[tot++]=0;
			now[y+sum][x+sum+n]=tot;
			ve[y+sum].push_back((table){x+sum+n,tot}),f[tot++]=1;
			ve[x+sum+n].push_back((table){y+sum,tot}),f[tot++]=0;
		}
		now[t+sum+n][tt]=tot;
		ve[t+sum+n].push_back((table){tt,tot}),f[tot++]=247483647;
		ve[tt].push_back((table){t+sum+n,tot}),f[tot++]=0;
		ans++;
		sum+=n;
	}
	printf("%d\n",ans);
	for(int i=1;i<=k;i++)
	{
		dfs(i,s,t+sum,1);
	}
	for(int i=1;i<=ans;i++)
	{
		printf("%d ",va[i].size()/2);
		for(int j=0;j<va[i].size();j++)
		{
			printf("%d ",va[i][j]);
		}
		printf("\n");
	}
	return 0;
}