#C241025A. 【模板】最小斯坦纳树

标签（Label）

斯坦纳树
动态规划
状态压缩

网址（Website）

P6192 【模板】最小斯坦纳树 - 洛谷

题目（Problem）

题目描述

给定一个包含 $n$ 个结点和 $m$ 条带权边的无向连通图 $G=(V,E)$。

再给定包含 $k$ 个结点的点集 $S$，选出 $G$ 的子图 $G’=(V’,E’)$，使得：

$S\subseteq V’$；
$G’$ 为连通图；
$E’$ 中所有边的权值和最小。

你只需要求出 $E’$ 中所有边的权值和。

输入格式

第一行：三个整数 $n,m,k$，表示 $G$ 的结点数、边数和 $S$ 的大小。

接下来 $m$ 行：每行三个整数 $u,v,w$，表示编号为 $u,v$ 的点之间有一条权值为 $w$ 的无向边。

接下来一行：$k$ 个互不相同的正整数，表示 $S$ 的元素。

输出格式

第一行：一个整数，表示 $E’$ 中边权和的最小值。

样例 #1

样例输入 #1

样例输出 #1

提示

【样例解释】

样例中给出的图如下图所示，红色点为 $S$ 中的元素，红色边为 $E’$ 的元素，此时 $E’$ 中所有边的权值和为 $2+2+3+4=11$，达到最小值。

【数据范围】

对于 $100%$ 的数据，$1\leq n\leq 100,\ \ 1\leq m\leq 500,\ \ 1\leq k\leq 10,\ \ 1\leq u,v\leq n,\ \ 1\leq w\leq 10^6$。

保证给出的无向图连通，但可能存在重边和自环。

题解（Solution）

$\qquad$这份代码调了好久，甚至我还是对着代码一个一个调的，最后发现是可恶的 q.emplace(-f[s][i],s); 真的不知道 $s\in[1,10^{18}]$ 是怎么过编译的，甚至没有 $\mathrm{RE}$ ，令人费解。

$\qquad$一句话题意：给定图，给定点集 $K$ （里面有 $k$ 个节点），选出子图满使 $k$ 个节点连通，且边权之和最小。（可以选这 $k$ 个节点以外的节点）

$\qquad$发现最多有 $10$ 个节点，考虑状态压缩 $\text{dp}$ ，容易发现最后选出来的边是一棵树（否则一定可以减去一条环上权值最大的边使答案变小），我们令 $f_{x,S}$ 表示以 $x$ 为根的子树，当前连接的关键点组成的点集为 $S$ ，在这种情况下的最小边权，容易发现初始有 $f_{i,T} = 0$ 表示对于 $i\in K$ 且 $T=\{i\}$ 的点最开始贡献为零，考虑转移：

$\qquad$对于单个节点 $i$ ，有 $f_{i,S} = f_{i,T}+f_{i,S-T}$ ，其中 $T\in S$ ；除此之外，还有节点之间的转移 $f_{i,S}=f_{j,S}+w_{i,j}$ 。我们最后要求的就是 $\min_{i\in K} f_{i,K}$ ，发现当 $S$ 一定时，我们要求的就是对于每个点的最短路径，这个可以用 $\text{dijkstra}$ 算法来处理，时间为 $m\log n$ ，我们只需要每次向集合 $S$ 中加入 $K$ 中的一个点，并且枚举当前集合 $S$ 的子集 $T$ ，并更新每个点的状态（时间复杂度 $O(n3^k)$ ），将所有单点的转移处理完再用 $\text{dijkstra}$ 去处理点与点之间的转移，枚举 $S$ 的时间复杂度是 $2^k$ ，总时间复杂度 $O(T(3^k+2^km\log n))$ 。

代码（Code）

#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 128;
const int S = 2048;
bool ST;

vector<P> ft[N];
int n,m,k,ans=inf;
int a[N];

int f[S][N];
void dijkstra(int s){
	priority_queue<P> q;
	For(i,0,n-1) if(f[s][i] != 0x3f3f3f3f3f3f3f3f) q.emplace(-f[s][i],i);
	while(q.size()){
		int x=q.top().y;q.pop();
		for(auto p:ft[x]){
			int y = p.x, v = p.y;
			if(f[s][x] + v < f[s][y]){
				f[s][y] = f[s][x] + v;
				q.emplace(-f[s][y], y);
			}
		}
	}
}

void Solve(){
	n = rd(), m = rd(), k = rd();
	For(i,1,m){
		int x = rd()-1, y = rd()-1, v = rd();
		ft[x].emplace_back(y,v);
		ft[y].emplace_back(x,v);
	}
	memset(f, 0x3f, sizeof(f));
	For(i,0,k-1) a[i] = rd()-1,f[1<<i][a[i]]=0;
	For(s,1,(1<<k)-1){
		for(int t=s&(s-1);t;t=(t-1)&s){
			if((s^t) > t) break;
			For(i,0,n-1) f[s][i] = min(f[s][i], f[s^t][i] + f[t][i]);
		}dijkstra(s);
	}printf("%lld\n", *min_element(f[(1<<k)-1], f[(1<<k)-1]+n));
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	int T = 1;double Tim = clock();
	while(T--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}