「BZOJ4774」修路

Description

村子间的小路年久失修,为了保障村子之间的往来,法珞决定带领大家修路。对于边带权的无向图 G=(V,E)G = (V, E),请选择一些边,使得1id1 \leq i \leq dii号节点和 ni+1n - i + 1 号节点可以通过选中的边连通,最小化选中的所有边的权值和。

Input

第一行三个整数 n,m,dn, m,d,表示图的点数和边数。
接下来的 mm行,每行三个整数 uiu_i, viv_i, wiw_i,表示有一条 uiu_iviv_i 之间,权值为 wiw_i 的无向边。

Output

一行一个整数,表示答案,如果无解输出1-1

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
10 20 1
6 5 1
6 9 4
9 4 2
9 4 10
6 1 2
2 3 6
7 6 10
5 7 1
9 7 2
5 9 10
1 6 8
4 7 4
5 7 1
2 6 9
10 10 6
8 7 2
10 9 10
1 2 4
10 1 8
9 9 7

Sample Output

1
8

HINT

1d41 \leq d \leq 4
2dn1042d \leq n \leq 10^4
0m1040 \leq m \leq 10^4
1ui,vin1 \leq u_i, v_i \leq n
1wi10001 \leq w_i \leq 1000

Solution

斯坦纳树的板子题。
斯坦纳树,应该就是求解跟生成树有关的问题。
fs,if_{s,i}表示以ii为根,对于必选节点的已联通状态是ss的最小花费。

  1. 从子集转移过来,fs,i=min{fs xor k,i+fk,i}f_{s,i}=\min\{f_{s\ xor\ k,i} + f_{k,i}\}
  2. 从边转移并且松弛一下,用dijkstradijkstra

因为求的是森林,所以状态是以根为依据合并的。松弛的目的就是换根。

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
#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 = 12000, M = 21000;
int f[1 << 8][N], n, m, d, g[1<<8];
struct Edge {
int u, v, nxt, w;
}e[M * 2];
int head[N], en;
void addedge(int x, int y, int z) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en, e[en].w = z;
}
int bin[10];
priority_queue<pii,vector<pii>,greater<pii> > q;
bool vis[N];
void dijkstra(int *f) {
for(int i = 1; i <= n; ++i) vis[i] = 0;
while(!q.empty()) {
pii now = q.top(); q.pop();
int x = now.nd;
if(vis[x]) continue;
vis[x] = 1;
for(int i = head[x]; i;i = e[i].nxt) {
int y = e[i].v;
if(f[y] > f[x] + e[i].w) {
f[y] = f[x] + e[i].w;
q.push(mk(f[y], y));
}
}
}
}
bool check(int x) {
return (x & (bin[d] - 1)) == (x >>d);
}
int main() {
n = read(), m = read(), d = read();
for(int i = 1; i <= m; ++i) {
int x = read(), y = read() ,z = read();
addedge(x, y, z);
addedge(y, x, z);
}
bin[0] = 1;
for(int i = 1; i <= d * 2; ++i) bin[i] = bin[i - 1] * 2;
memset(f,0x3f,sizeof f);
memset(g,0x3f,sizeof g);
for(int i = 1; i <= d; ++i) f[bin[i - 1]][i] = f[bin[i + d - 1]][n - i + 1] = 0;
int B = bin[d * 2];
for(int s = 0; s < B; ++s) {
for(int j = 1; j <= n; ++j) {
for(int k = s; k; k = (k - 1) & s) {
f[s][j] = min(f[s][j], f[s ^ k][j] + f[k][j]);
}
if(f[s][j] < 0x3f3f3f3f) q.push(mk(f[s][j], j));
}
dijkstra(f[s]);
for(int j = 1; j <= n; ++j) {
g[s] = min(g[s], f[s][j]);
}
}
for(int s = 0; s < B; ++s)
for(int t = s; t; t = (t - 1) & s)
if(check(t) && check(s ^ t))
g[s] = min(g[s], g[s ^ t] + g[t]);
if(g[bin[d*2] - 1] == 0x3f3f3f3f) puts("-1");
else writeln(g[bin[d*2] - 1]);
return 0;
}