BZOJ 1927: [Sdoi2010]星际竞速

Description

10 年一度的银河系赛车大赛又要开始了。作为全银河最盛大的活动之一，夺得这个项目的冠军无疑是很多人的梦想，来自杰森座 α星的悠悠也是其中之一。赛车大赛的赛场由 N 颗行星和M条双向星际航路构成，其中每颗行星都有一个不同的引力值。大赛要求车手们从一颗与这 N 颗行星之间没有任何航路的天体出发，访问这 N 颗行星每颗恰好一次，首先完成这一目标的人获得胜利。由于赛制非常开放，很多人驾驶着千奇百怪的自制赛车来参赛。这次悠悠驾驶的赛车名为超能电驴，这是一部凝聚了全银河最尖端科技结晶的梦幻赛车。作为最高科技的产物，超能电驴有两种移动模式：高速航行模式和能力爆发模式。在高速航行模式下，超能电驴会展开反物质引擎，以数倍于光速的速度沿星际航路高速航行。在能力爆发模式下，超能电驴脱离时空的束缚，使用超能力进行空间跳跃——在经过一段时间的定位之后，它能瞬间移动到任意一个行星。天不遂人愿，在比赛的前一天，超能电驴在一场离子风暴中不幸受损，机能出现了一些障碍：在使用高速航行模式的时候，只能由每个星球飞往引力比它大的星球，否则赛车就会发生爆炸。尽管心爱的赛车出了问题，但是悠悠仍然坚信自己可以取得胜利。他找到了全银河最聪明的贤者——你，请你为他安排一条比赛的方案，使得他能够用最少的时间完成比赛。

Input

第一行是两个正整数 N, M。第二行 N 个数 A1~AN，其中Ai表示使用能力爆发模式到达行星 i 所需的定位时间。接下来 M行，每行 3个正整数ui, vi, wi，表示在编号为 ui和vi的行星之间存在一条需要航行wi时间的星际航路。输入数据已经按引力值排序，也就是编号小的行星引力值一定小，且不会有两颗行星引力值相同。

Output

仅包含一个正整数，表示完成比赛所需的最少时间。

Sample Input

3 3

1 100 100

2 1 10

1 3 1

2 3 1

Sample Output

HINT

说明：先使用能力爆发模式到行星 1，花费时间 1。

然后切换到高速航行模式，航行到行星 2，花费时间10。

之后继续航行到行星 3完成比赛，花费时间 1。

虽然看起来从行星 1到行星3再到行星 2更优，但我们却不能那样做，因为

那会导致超能电驴爆炸。

对于 30%的数据 N≤20，M≤50；

对于 70%的数据 N≤200，M≤4000；

对于100%的数据N≤800， M≤15000。输入数据中的任何数都不会超过106

。

输入数据保证任意两颗行星之间至多存在一条航道，且不会存在某颗行星到

自己的航道。

Solution

我一开始建图的时候是考虑的对于一个i是叫他由别的点飞来还是传送来，然后发现建出的图都是些什么鬼！（很难建图！）

然后看了题解才发现自己的思路有些问题。建图方法好神奇！

每个点拆成出点和入点，S向每个出点连边（v=1,c=0），代表从该点出发可以有一条指向其他点的边。S向每个入点连边(v=1,c=Ai)，代表可以以此点为起点。每个入点向T连边(v=1,c=0)，代表到达该点。对应边的起点的出点向终点的入点连边(v=1,c=w)，代表可以从起点出发到达终点，由此，任意一个入点要么从S出发（代价为Ai)要么从另一点的出点出发（代价为w），符合题意。
———nlj1999

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
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int INF = 1<<30;
int getint() {
	int r = 0, k = 1; char c = getchar();
	for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
	for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
	return r * k;
}
struct edge_type {
	int to, next, r, c;
} edge[100005];
int S, T, dis[10005], a[10005], pre[10005], cnte = 1, h[10005];
bool vis[10005];
queue<int> Q;
void ins(int u, int v, int f, int c) {
	edge[++cnte].to = v;
	edge[cnte].next = h[u];
	h[u] = cnte;
	edge[cnte].r = f;
	edge[cnte].c = c;
	edge[++cnte].to = u;
	edge[cnte].next = h[v];
	h[v] = cnte;
	edge[cnte].r = 0;
	edge[cnte].c = -c;
}
bool SPFA(int &flow, int &cost) {
	for (int i = S; i <= T; ++i) dis[i] = INF, vis[i] = false;
	pre[S] = 0; dis[S] = 0; vis[S] = true; a[S] = INF;
	Q.push(S);
	int now;
	while (!Q.empty()) {
		now = Q.front(); Q.pop();
		vis[now] = false;
		for (int i = h[now]; i; i = edge[i].next) {
			if (!edge[i].r) continue;
			if (dis[edge[i].to] > dis[now] + edge[i].c) {
				dis[edge[i].to] = dis[now] + edge[i].c;
				a[edge[i].to] = min(a[now], edge[i].r);
				pre[edge[i].to] = i;
				if (!vis[edge[i].to]) {
					vis[edge[i].to] = true;
					Q.push(edge[i].to);
				}
			}
		}
	}
	if (dis[T] == INF) return false;
	flow += a[T];
	cost += a[T] * dis[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(flow, cost));
	return cost;
}

int n, m, x, y, z;
int main() {
	n = getint(); m = getint(); S = 0; T = 1610;
	for (int i = 1; i <= n; ++i) {
		x = getint();
		ins(S, i, 1, 0);
		ins(S, i+805, 1, x);
		ins(i+805, T, 1, 0);
	}
	for (int i = 1; i <= m; ++i) {
		x = getint(); y = getint(); z = getint();
		if (x > y) swap(x, y);
		ins(x, y+805, 1, z);
	}
	int ans = MCMF();
	printf("%d", ans);
}