CODEVS 1035 火车停留

题目描述 Description

“今天你要去远行，送你风雨中…..”，伴着凄美的歌声，郭靖夫妇终于踏上征程。为了尽快到达边疆为国效力，他们搭上了2002次列车。可在途径sweet station时，被该站站长缠住了身，是什么原因呢？

因为该车站由于经营不善，面临破产，该站负责人早闻黄蓉聪明过人，一定要她帮忙出出主意，挽救车站。

该车站有n个车道，由于车道的长度有限，每个车道在某一时刻最多只能停靠一列火车。该站每天将有m列火车从车站经过，其中第i列火车到达车站的时间为Reach[i]，火车上装有价值Cost[i]的货物。

如果该火车进站，则车站将获得Cost[i]的1%收益，但由于货物的搬运时间，该火车将在车站停留一段时间Stay[i]，这段时间内，火车将占用车站中的某一个车道。当然，火车也可以不在站中停靠而直接出站，但这样车站将得不到一分钱。

要挽救车站，就是要对车站的列车进行调度，使获得的效益最大。当然，解决这个问题对于黄蓉来说并不难，但边疆吃紧，时间不等人，你能帮帮黄蓉，让她脱身吗？

任务:运行你的程序得到该站的最大效益。

输入描述 Input Description

第1行中为两个正整数：n（n≤20）m（m≤100），第2行到第m+1行，每行有3个不超过1000正整数。第i+1行的3个数分别为：Reach[i]， Cost[i]和Stay[i]，它们用单个空格分隔。

输出描述 Output Description

仅有一行，为车站的最大收益（精确到小数点后2位）。注意，如果火车a从第i车道离开时，火车b刚好到站（即Reach[a]+Stay[a] =Reach[b]），则它不能进入第i车道。

样例输入 Sample Input

1 3

2 5 1

3 4 1

5 6 2

样例输出 Sample Output

0.11

Solution

这道题建模太经典啦！首先我们考虑到车站数量是有限的，那么我们就用流来限制。

建立源点S，次源点SS（自己起的名字…），汇点T，次汇点TT。

把每辆火车拆成两个点，一个x一个y，x、y之间流量为1，费用为-cost（最大费用），然后我们处理每两辆火车：

如果火车能同时存在，那么我们从第一辆火车的y连向第二辆火车的x，流量无穷，费用0（表示获取到前者车的利益后还可以获取后者的利益）。

最后我们跑一边MCMF就可以了。

（窝在写的时候一开始出现了负环，经过检查，发现有些边建立了两次，其实如果这样子的话，就会在两辆火车之间不断循环，如果我们把网络流看成像个二分图一样的玩意（x左边y放右边），那么这个负环的效果就是类似于“8”字型。或者您也可以这样理解：我们的火车Reach是有先后顺序的，我们在建边的时候不能不考虑，比如两辆火车，A、B，A在B前Reach且他们不相交。那么合理的进站顺序为A->B，如果不考虑时间的话，会出现形如A->B->A->B…的负环。）

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>
#include <queue>
#include <algorithm>
using namespace std;

typedef long long ll;
int getint() {
	int r = 0, k = 1; char c = getchar();
	for (; c < '0' || c > '9'; c = getchar()) if (c == '-') k = -1;
	for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
	return r*k;
}
const int INF = 1000000007;
const int maxn = 505;
const int maxnode = 666;
queue<int> Q;
int S, T, cnte = 1;
struct edge_type {
	int to, next, r, cost;
} edge[100007];
int h[maxnode];
void ins(int u, int v, int f, int c) {
	edge[++cnte].to = v;
	edge[cnte].next = h[u];
	edge[cnte].r = f;
	edge[cnte].cost = c;
	h[u] = cnte;
	edge[++cnte].to = u;
	edge[cnte].next = h[v];
	edge[cnte].r = 0;
	edge[cnte].cost = -c;
	h[v] = cnte;
}
bool vis[maxnode];
int d[maxnode], pre[maxnode], a[maxnode];
bool SPFA(int S, int T, int &flow, int &cost) {
	while (!Q.empty()) Q.pop();
	Q.push(S);
	for (int i = S; i <= T; ++i) d[i] = INF, vis[i] = false;
	d[S] = 0;
	vis[S] = true;
	a[S] = INF;
	pre[S] = 0;
	int now;
	while (!Q.empty()) {
		now = Q.front(); Q.pop();
		vis[now] = false;
		for (int i = h[now]; i; i = edge[i].next) {
			if (d[edge[i].to] > d[now] + edge[i].cost && edge[i].r) {
				d[edge[i].to] = d[now] + edge[i].cost;
				pre[edge[i].to] = i;
				a[edge[i].to] = min(a[now], edge[i].r);
				if (!vis[edge[i].to]) {
					vis[edge[i].to] = true;
					Q.push(edge[i].to);
				}
			}
		}
	}
	if (d[T] == INF) return false;
	flow += a[T];
	cost += d[T] * a[T];
	for (now = T; now != S; now = edge[pre[now]^1].to) {
		edge[pre[now]].r -=a[T];
		edge[pre[now]^1].r += a[T];
	}
	return true;
}
int MCMF() {
	int flow = 0, cost = 0;
	while (SPFA(S, T, flow, cost));
	return cost;
}
int n, m, L[maxn], C[maxn], R[maxn];
bool cover(int i, int j) {
	return R[i] < L[j];
}
int main() {
	n = getint();
	m = getint();
	S = 1;
	int SS = m+m+2, TT = m+m+3;
	T = m+m+4;
	ins(S, SS, n, 0);
	ins(TT, T, n, 0);
	for (int i = 1; i <= m; ++i) {
		L[i] = getint(); C[i] = getint(); R[i] = getint();
		R[i] += L[i];
		ins(SS, i+1, INF, 0);
		ins(i+m+1, TT, INF, 0);
		ins(i+1, i+m+1, 1, -C[i]);
	}
	for (int i = 1; i <= m; ++i)
		for (int j = 1; j <= m; ++j)
			if (cover(i, j))
				ins(i+m+1, j+1, INF, 0);
	int ans = -MCMF();
	printf("%d.%.2d", ans/100, ans%100);
}