「BZOJ1927」 [SDOI2010]星际竞速

Description

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

Input

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

Output

输出文件starrace.out仅包含一个正整数,表示完成比赛所需的最少时间。

Sample Input

1
2
3
4
5
3 3
1 100 100
2 1 10
1 3 1
2 3 1

Sample Output

1
12

HINT

对于30%30\%的数据N20,M50N\leq 20,M\leq 50

对于70%70\%的数据N200,M4000N\leq 200,M\leq 4000

对于100%100\%的数据N800,M15000N\leq 800,M\leq 15000
输入数据中的任何数都不会超过10610^6
输入数据保证任意两颗行星之间至多存在一条航道,且不会存在某颗行星到自己的航道。

Solution

对于把点拆成iiii',设源点是ss,汇点是tt
ssii连容量为11,费用为00的边
ssii'连容量为11,费用为aia_i的边
ii'tt连容量为11,费用为00的边
uuvv'连容量为11,费用为ww的边
跑一边最小费用最大流。

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<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#include<queue>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}

const int N = 800 * 3, M = 15000*4;
int n, m;
struct Edge {
int u, v, nxt, w, f;
}e[M * 2];
int head[N], en;
void addedge(int x, int y, int w, int f) {
e[++en].u = x, e[en].v = y, e[en].w = w, e[en].f = f, e[en].nxt = head[x], head[x] = en;
e[++en].v = x, e[en].u = y, e[en].w = -w, e[en].f = 0, e[en].nxt = head[y], head[y] = en;
}
int a[N];
const int inf = 1e9;
bool inq[N];
int d[N], inc[N], pre[N], s, t;
bool spfa() {
queue<int>q;
q.push(s);
for(int i = 1; i <= t; ++i) inq[i] = 0, d[i] = inf;
d[s] = 0;
inc[s] = inf;
while(!q.empty()) {
int x = q.front(); q.pop();
inq[x] = 0;
for(int i = head[x]; i; i = e[i].nxt) if(e[i].f){
int y = e[i].v;
if(d[y] > d[x] + e[i].w) {
d[y] = d[x] + e[i].w;
pre[y] = i;
inc[y] = min(inc[x], e[i].f);
if(!inq[y])q.push(y), inq[y] = 1;
}
}
}
return d[t] < inf;
}
void KM(ll &ans) {
int x = t;
while(x != s) {
e[pre[x]].f -= inc[t];
e[pre[x] ^ 1].f += inc[t];
x = e[pre[x]].u;
}
ans += inc[t] * d[t];
}
int main() {
en = 1;
n = read(), m = read();
s = n * 2 + 1;
t = n * 2 + 2;
for(int i = 1; i <= n; ++i) {
a[i] = read();
addedge(s, i + n, a[i], 1);
addedge(s, i, 0, 1);
}
for(int i = 1; i <= m; ++i) {
int x = read(), y = read();
int z = read();
if(x > y) swap(x, y);
addedge(x, y + n, z, 1);
}
for(int i = 1; i <= n; ++i) addedge(i + n, t, 0, 1);
ll ans = 0;
while(spfa()) KM(ans);
writeln(ans);
return 0;
}