修路

Time Limit: 20 Sec Memory Limit: 256 MB

Description

村子间的小路年久失修，为了保障村子之间的往来，法珞决定带领大家修路。对于边带权的无向图 G = (V, E)，

请选择一些边，使得1 <= i <= d， i号节点和 n - i + 1 号节点可以通过选中的边连通，最小化选中的所有边

的权值和。

Input

第一行两个整数 n, m，表示图的点数和边数。接下来的 m行，每行三个整数 ui, vi, wi，表示有一条 ui 与 vi

之间，权值为 wi 的无向边。

Output

仅一行一个整数表示答案。

Sample Input

5 5 2
　　1 3 4
　　3 5 2
　　2 3 1
　　3 4 4
　　2 4 3

Sample Output

9

HINT

1 <= d <= 4

2d <= n <= 10^4

0 <= m <= 10^4

1 <= ui, vi <= n

1 <= wi <= 1000

Main idea

给定若干对点，选择若干边，询问满足每对点都连通的最小代价。

Solution

发现 d 非常小，所以我们显然可以使用斯坦纳树来求解。

斯坦纳树是用来解决这种问题的：给定若干关键点，求使得关键点连通的最小代价。

我们可以令 f[i][opt] 表示以 i 为根时，关键点连通态为opt的最小代价。（以二进制表示是否连通）

然后我们就可以用两种方法来更新 f[i][opt]：

1. 设定集合x,y，x∪y=opt且x∩y=∅，那么我们显然就可以将用x,y合并来更新opt，
　　2. 若 f[j][opt] 中opt = f[i][opt]中opt，那么我们就可以以连边方式合并两个集合，这种合并方式显然可以用最短路实现，使得答案更优。

然后我们就可以求出所有状态的f[i][opt]，接下来再利用DP，求解。

定义Ans[opt]表示连通态为opt时最小代价，如果对应点同时连通或不连通则可以更新，枚举所有情况就可以求出答案了。

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<bits/stdc++.h>
using namespace std;

const int ONE = 20005;
const int MOD = 1e9+7;

int n,m,d;
int x,y,z;
int a[ONE];
int next[ONE],first[ONE],go[ONE],w[ONE],tot;
int All,f[ONE/2][258],INF;
int q[10000005],vis[ONE],tou,wei;
int Ans[258];

int get()
{
    int res=1,Q=1;    char c;
    while( (c=getchar())<48 || c>57)
        if(c=='-')Q=-1;
    if(Q) res=c-48;
    while((c=getchar())>=48 && c<=57)
        res=res*10+c-48;
    return res*Q;
}

void Add(int u,int v,int z)
{
    next[++tot]=first[u];    first[u]=tot;    go[tot]=v;    w[tot]=z;
    next[++tot]=first[v];    first[v]=tot;    go[tot]=u;    w[tot]=z;
}


namespace Steiner
{
    void pre()
    {
        memset(f,63,sizeof(f));    INF=f[0][0];
        int num = 0;
        for(int i=1;i<=d;i++) f[i][1<<num] = 0,    num++;
        for(int i=n-d+1;i<=n;i++) f[i][1<<num] = 0, num++;
        All = (1<<num) - 1;
    }

    void Spfa(int opt)
    {
        while(tou<wei)
        {
            int u=q[++tou];
            for(int e=first[u];e;e=next[e])
            {
                int v=go[e];
                if(f[v][opt] > f[u][opt] + w[e])
                {
                    f[v][opt] = f[u][opt] + w[e];
                    if(!vis[v])
                    {
                        vis[v] = 1;
                        q[++wei] = v;
                    }
                }
            }
            vis[u] = 0;
        }
    }

    void Deal()
    {
        for(int opt=0;opt<=All;opt++)
        {
            for(int i=1;i<=n;i++)
            {
                for(int sub=opt;sub;sub=(sub-1) & opt)
                    f[i][opt] = min(f[i][opt],f[i][sub]+f[i][opt^sub]);
                if(f[i][opt] != INF)
                {
                    q[++wei] = i;
                    vis[i] = 1;
                }
            }
            Spfa(opt);
        }
    }
}

bool Check(int opt)
{
    for(int i=0,j=(d<<1)-1; i<d; i++,j--)
        if( ((opt & (1<<i))== 0) !=  ((opt & (1<<j))==0) )
            return 0;
    return 1;
}

int main()
{
    n=get();    m=get();    d=get();
    for(int i=1;i<=m;i++)
    {
        x=get();    y=get();    z=get();
        Add(x,y,z);
    }

    Steiner::pre();
    Steiner::Deal();

    memset(Ans,63,sizeof(Ans));
    for(int opt=0;opt<=All;opt++)
        if(Check(opt))
        {
            for(int i=1;i<=n;i++)
                Ans[opt] = min(Ans[opt], f[i][opt]);
        }

    for(int opt=0;opt<=All;opt++)
        for(int sub=opt;sub;sub=(sub-1) & opt)
            Ans[opt] = min(Ans[opt], Ans[sub]+Ans[opt^sub]);

    if(Ans[All] == INF) printf("-1");
    else printf("%d",Ans[All]);
}