CODEVS 1034 家园

题目描述 Description

由于人类对自然的疯狂破坏，人们意识到在大约2300年之后，地球不能再居住了，于是在月球上建立了新的绿地，以便在需要时移民。令人意想不到的是，2177年冬由于未知的原因，地球环境发生了连锁崩溃，人类必须在最短的时间内迁往月球。

现有n个太空站处于地球与月球之间（编号1..n），m艘公共交通太空船在其中来回穿梭，每个太空站Si可容纳无限的人，每艘太空船pi只可容纳Hpi人。对于每一艘太空船pi，将周期性地停靠一系列的太空站（Si1,Si2…Sir），如：（1，3，4）表示停靠太空站1 3 4 1 3 4 1 3 4 …。任一艘太空船从任一个太空站驶往另一个任意的太空站耗时为1。人只能在太空船停靠太空站（或地球、月球）时上船或下船。初始时的人全在地球上，太空船全在初始站（太空船pi处于Si1），目标是让所有的人尽快地全部转移到月球上。

输入描述 Input Description

文件第一行为三个正整数 n（太空站个数）、 m（太空船个数）、 k（需要运送的地球上的人的个数），其中 1<=m<=13, 1<=n<=20, 1<=k<=50。

接下来的n行给出了太空船的信息，第i+1行说明太空船pi，此行第一个数表示pi可容纳的人数Hpi，第二个数表示pi停靠一个周期的太空站个数r，1<=r<=n+2, 随后r个数便是停靠的太空站的编号(Si1,Si2,…,Sir), 地球用0表示，月球用-1表示。0时刻时，所有太空船都在初始站，随后开始运行，在时刻1，2，3…等正点时刻各艘太空船停靠相应的太空站，即人只有在0,1,2…等正点时刻才能上下太空船。

输出描述 Output Description

文件只有一个数，若问题有解，输出完成全部人员安全转移的时刻，否则输出0。

样例输入 Sample Input

2 2 1

1 3 0 1 2

1 3 1 2 -1

样例输出 Sample Output

数据范围及提示 Data Size & Hint

1<=m<=13, 1<=n<=20, 1<=k<=50。

Solution

这道题建图也比较的经典。

我们以时间建图，每次建图不删掉以前的边，而是在原网络图上添加新边。

对于每个时刻time，我们可以把所有的停靠站和星球都多拆出一份，然后根据每一艘飞船的飞的顺序连边。

方法：假设我们有一艘飞船在time-1时刻在u星球，time时刻它飞到了v，那么我们就在u星球time-1时刻的点和v星球time时刻的点之间连一条边，容量为飞船容量。

源点S为地球1时刻的点，T为月球time时刻的点。

对于这张图跑一边最大流，如果Maxflow>=K，那么就说明人们都转移到了月球上了，输出time。

如果我们找了150多次time都没有出答案，我们就可以说原图无法将地球上的人转移到月球上了（数据挺弱）。

Code

 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
#include <cstdio>
const int maxe = 91005;
const int maxnode = 50005;
struct edge_type {
	int to, next, r;
} edge[maxe];
int S = 1, T = 900, cnte = 1, h[maxnode];
int Q[maxnode+100];
void ins(int u, int v, int f) {
	++cnte;
	edge[cnte].to = v;
	edge[cnte].r = f;
	edge[cnte].next = h[u];
	h[u] = cnte;
	++cnte;
	edge[cnte].to = u;
	edge[cnte].r = 0;
	edge[cnte].next = h[v];
	h[v] = cnte;
}
int tail, head, d[maxnode], cur[maxnode];
bool bfs() {
	tail = head = 0;
	for (int i = S; i <= T; ++i) d[i] = -1;
	Q[tail++] = S;
	d[S] = 0;
	int now;
	while (head < tail) {
		now = Q[head++];
		for (int i = h[now]; i; i = edge[i].next) {
			if (d[edge[i].to] == -1 && edge[i].r) {
				d[edge[i].to] = d[now] + 1;
				Q[tail++] = edge[i].to;
			}
		}
	}
	return d[T] != -1;
}
int min(int a, int b) {
	return a < b ? a : b;
}
int dfs(int now, int a) {
	if (T == now || a == 0) return a;
	int ret = 0, f;
	for (int &i = cur[now]; i; i = edge[i].next) {
		if (d[edge[i].to] != d[now]+1) continue;
		if (f = dfs(edge[i].to, min(a, edge[i].r))) {
			a -= f;
			ret += f;
			edge[i].r -= f;
			edge[i^1].r += f;
			if (a == 0) break;
		}
	}
	if (ret == 0) d[now] = -1;
	return ret;
}
const int INF = 1<<30;
int Dinic() {
	int ret = 0;
	while (bfs()) {
		for (int i = S; i <= T; ++i)
			cur[i] = h[i];
		ret += dfs(S, INF);
	}
	return ret;
}
int m, n, K, r[50], p[50][50], H[50];
int time = 0;
int id(int now, int nt) {
	if (now == -1) return (n+2)+25*nt;
	return (now+1)+25*nt;
}
void add_edge() {
	S = id(0, 0);
	T = id(-1, time);
	for (int i = -1; i <= n; ++i) ins(id(i, time-1), id(i, time), INF);
	for (int i = 0; i < m; ++i) ins(id(p[i][(time-1)%r[i]], time-1), id(p[i][time%r[i]], time), H[i]);
}
int main () {
	scanf("%d%d%d", &n, &m, &K);
	for (int i = 0; i < m; ++i) {
		scanf("%d%d", H+i, r+i);
		for (int j = 0; j < r[i]; ++j) scanf("%d", &p[i][j]);
	}
	while (true) {
		if (time >= 150) {
			printf("0");
			return 0;
		}
		++time;
		add_edge();
		K -= Dinic();
		if (K <= 0) {
			printf("%d", time);
			return 0;
		}
	}
}