bzoj 4774 修路

Posted on | Edited on | Views:

斯坦纳树 + 状压 .

  • 开始感觉直接做一颗最小生成树出来,把没用的边割掉就好了.然而随手画几个图发现是错的.

  • 然后学习了一波 最小斯坦纳树 .这东西可以看做是最小生成树的一般情况.生成树是求一个选边方案,将所有的点加入联通块中.斯坦纳树是把指定点集中的点加入联通块中,也可以加入不在点集中的点来辅助.

    求解最小斯坦纳树是 $NP$ 的,没有多项式算法,用状压做.
    设 $f[S][i]$ 为指定点的连通状态为 $S$ ,最小斯坦纳树的根节点为 $i$ 时的最小权值.转移有两种.
    第一种是将当前集合拆成两个不相交的子集, $f[S][i]\leftarrow f[S_1][i]+f[S_2][i],S_1,S_2\subset S,S_1 \& S_2=0$ .
    另一种是换根, $f[S][i]\leftarrow f[S][j]+val_{i,j}$ ,后者表示连接 $i,j$ 的边权.这东西有后效性,用 $Spfa$ 转移.

  • 而这道题是指定点对间连通,可以看做最小斯坦纳森林.设 $g[S]$ 表示连通了点集 $S$ 的最小斯坦纳森林的权值.

  • 转移有 $g[S]\leftarrow g[S_1]+g[S_2],S_1,S_2\subset S,S_1 \& S_2=0​$ .即将 $S​$ 拆成两个不相交子集. $S_1,S_2​$ 都需要满足每对对应点要么都不在其中,要么都在其中.
  • 最后答案就是 $g[S_0]$ , $S_0$ 表示将那 $2d$ 个点都连通的状态.

小心爆 $int$ .

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=1e4+10,MAXS=1<<8;
int inf;
int ecnt=0,head[MAXN],to[MAXN<<1],nx[MAXN<<1],val[MAXN<<1];
inline void addedge(int u,int v,int w)
{
	++ecnt;
	to[ecnt]=v;
	nx[ecnt]=head[u];
	val[ecnt]=w;
	head[u]=ecnt;
}
int f[MAXS][MAXN],g[MAXS];
int n,m,D;
queue<int> q;
int vis[MAXN];
void SPFA(int S)
{
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=nx[i])
		{
			int v=to[i];
			if(f[S][v]-f[S][u]>val[i])
			{
				f[S][v]=f[S][u]+val[i];
				if(!vis[v])
				{
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
}
bool check(int S)
{
	return (S&((1<<D)-1))==(S>>D);
}
int main()
{
	n=read(),m=read(),D=read();
	for(int i=1;i<=m;++i)
	{
		int u=read(),v=read(),w=read();
		addedge(u,v,w);
		addedge(v,u,w);
	}
	memset(f,63,sizeof f);
	memset(g,63,sizeof g);
	inf=f[0][0];
	for(int i=1;i<=D;++i)
		f[1<<(i-1)][i]=f[1<<(D+i-1)][n-i+1]=0;
	int mx=1<<(2*D);
	for(int S=0;S<mx;++S)
	{
		for(int i=1;i<=n;++i)
		{
			for(int S1=(S-1)&S;S1;S1=(S1-1)&S)
				f[S][i]=min(f[S][i],f[S1][i]+f[S^S1][i]);
			if(f[S][i]<inf)
			{
				q.push(i);
				vis[i]=1;
			}
		}
		SPFA(S);
		for(int i=1;i<=n;++i)
			g[S]=min(g[S],f[S][i]);
	}
	for(int S=0;S<mx;++S)
		for(int S1=(S-1)&S;S1;S1=(S1-1)&S)
			if(check(S1) && check(S^S1))
				g[S]=min(g[S],g[S1]+g[S^S1]);
	if(g[mx-1]>=inf)
		puts("-1");
	else
		cout<<g[mx-1];
	return 0;
}