「BZOJ2324」[ZJOI2011]营救皮卡丘

Description

皮卡丘被火箭队用邪恶的计谋抢走了!这三个坏家伙还给小智留下了赤果果的挑衅!为了皮卡丘,也为了正义,小智和他的朋友们义不容辞的踏上了营救皮卡丘的道路。

火箭队一共有NN个据点,据点之间存在MM条双向道路。据点分别从11NN标号。小智一行KK人从真新镇出发,营救被困在N号据点的皮卡丘。为了方便起见,我们将真新镇视为00号据点,一开始KK个人都在00号点。

由于火箭队的重重布防,要想摧毁KK号据点,必须按照顺序先摧毁11K1K-1号据点,并且,如果K1K-1号据点没有被摧毁,由于防御的连锁性,小智一行任何一个人进入据点K,都会被发现,并产生严重后果。因此,在K1K-1号据点被摧毁之前,任何人是不能够经过KK号据点的。

为了简化问题,我们忽略战斗环节,小智一行任何一个人经过KK号据点即认为KK号据点被摧毁。被摧毁的据点依然是可以被经过的。

KK个人是可以分头行动的,只要有任何一个人在K1K-1号据点被摧毁之后,经过KK号据点,KK号据点就被摧毁了。显然的,只要N号据点被摧毁,皮卡丘就得救了。

野外的道路是不安全的,因此小智一行希望在摧毁NN号据点救出皮卡丘的同时,使得KK个人所经过的道路的长度总和最少。

请你帮助小智设计一个最佳的营救方案吧!

Input

第一行包含三个正整数NNMMKK。表示一共有N+1N+1个据点,分别从00NN编号,以及MM条无向边。一开始小智一行共KK个人均位于00号点。
接下来MM行,每行三个非负整数,第ii行的整数为AiA_iBiB_iLiL_i。表示存在一条从AiA_i号据点到BiB_i号据点的长度为LiL_i的道路。

Output

仅包含一个整数SS,为营救皮卡丘所需要经过的最小的道路总和。

Sample Input

1
2
3
4
5
3 4 2
0 1 1
1 2 1
2 3 100
0 3 1

Sample Output

1
3

HINT

对于100%100\%的数据满足N150N \leq 150, M20000M \leq 20000, 1K101 \leq K \leq 10, Li10000L_i \leq 10 000, 保证小智一行一定能够救出皮卡丘

Solution

为了方便,所有点的编号+1+1
定义disi,jdis_{i,j}表示从ii出发,到达jj且,不经过点编号max{i,j}\ge\max\{i,j\}的点的最小距离。用FloydFloyd预处理出来。
对于i,j(i<j)i,j(i<j)连边(i,j+n,1,disi,j)(i,j+n,1,dis_{i,j})分别表示容量为11,费用为disi,jdis_{i,j},下同。
连边(s,1,K,0)(s,1,K,0)
对于ii,连边(i+n,t,1,0)(i+n,t,1,0)
跑一遍最小费用最大流就是答案。
这个模型就是最小链覆盖。
因为答案要求的方案一定是不多于KK条从11出发的链。且不相交,如果相交了,那么其中一个就可以把相交的删掉就行了。

如图,如果12341\to2\to3\to41351\to3\to5冲突了,你会发现先走前者,再走后者不如直接走1234351\to2\to3\to4\to3\to5优秀。
因为是个DAGDAG,都是从编号小的到编号大的,所以一定可以对跑出来的网络流进行方案构造。
假如跑了kk条链,那么如果当前走到的最大值是vv,那么想走下一个点的话,任意找其中一条,如果在这条已经走的基础上的下一个点是v+1v+1就走这一条,不断循环就合法。

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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<queue>
#include<bitset>
#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 = 161*2, M = N * N * 2;

int g[N][N];
int n, m, K;
struct Edge {
int u, v, nxt, w, f;
}e[M *2];
int head[N], en = 1;
void addedge(int x, int y, int f, int w) {
e[++en].u = x, e[en].v = y, e[en].f = f, e[en].w = w, e[en].nxt = head[x], head[x] = en;
e[++en].u = y, e[en].v = x, e[en].f = 0, e[en].w = -w, e[en].nxt = head[y], head[y] = en;
}
int s, t;
bool inq[N];
int d[N], inc[N], pre[N];
const int inf = 1e9;
bool spfa() {
for(int i = 1; i <= t; ++i) d[i] = 1e9;
d[s] = 0;
inc[s] = 1e9;
queue<int>q;
q.push(s);
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) {
if(d[e[i].v] > d[x] +e[i].w) {
d[e[i].v] = d[x] + e[i].w;
inc[e[i].v] = min(inc[x], e[i].f);
pre[e[i].v] = i;
if(!inq[e[i].v]) q.push(e[i].v), inq[e[i].v] = 1;
}
}
}
return d[t] < 1e9;
}
int KM() {
int x = t;
while(x != s) {
e[pre[x]].f -= inc[t];
e[pre[x] ^ 1].f += inc[t];
x = e[pre[x]].u;
}
return d[t] * inc[t];
}
int main() {
n = read(), m = read(), K = read();
memset(g,0x3f,sizeof g);
for(int i = 1; i <= m; ++i) {
int x = read() + 1, y = read() + 1, z = read();
g[x][y] = g[y][x] = min(g[x][y], z);
}
++n;
s = n * 2 + 1, t = n * 2 + 2;
for(int k = 1; k <= n; ++k)
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
if(k < max(i, j))
g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
addedge(s, 1, K, 0);
addedge(1 + n, t, 1, 0);
for(int i = 1; i <= n; ++i)
for(int j = i + 1; j <= n; ++j)
if(g[i][j] < 0x3f3f3f3f) {
addedge(i, j + n, inf, g[i][j]);
}
for(int i = 2; i <= n; ++i) {
addedge(i + n, t, 1, 0);
addedge(s, i, 1, 0);
}
ll ans = 0;
while(spfa()) ans += KM();
writeln(ans);
return 0;
}