【模板】最小斯坦纳树

本文主要是介绍【模板】最小斯坦纳树，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

模型，给定 \(n\) 个点 \(m\) 条边的无向图，和 \(k\) 个关键点。选出边权和最小的一些边使得 \(k\) 个点连通。

因为选出的边一定是一棵树，所以称为最小斯坦纳树。

直接状压 \(f[i][S]\) 表示以 \(i\) 为根，与 \(i\) 联通的关键点集合为 \(S\)。

我们可以枚举子集直接转移 \(f[i][S] = \min\limits_{T\subset S}\{f[i][T] + f[i][S\oplus T]\}\)。

也可以再外接一条边，\(f[i][s] + e_{i,j} \to f[j][s]\)。

第一种转移的阶段很清晰，直接枚举子集即可。第二种转移有后效性，我们对每层 \(s\) 跑最短路即可。

时间复杂度 \(\mathcal{O}(n3^k + 2^km\log m)\)。

/*
    Author : SharpnessV
    Right Output ! & Accepted !
*/
#include<bits/stdc++.h>
//#define int long long

#define rep(i, a, b) for(int i = (a);i <= (b);i++)
#define pre(i, a, b) for(int i = (a);i >= (b);i--)
#define rp(i, a) for(int i = 1; i <= (a); i++)
#define pr(i, a) for(int i = (a); i >= 1; i--)
#define go(i, x) for(auto i : x)

#define mp make_pair
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define ze(p) memset(p, 0, sizeof(p))
#define mem(p, x) memset(p, x, sizeof(p))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define si(x) (int)(x).size()
#define db cerr
#define pc putchar
#define gc getchar
#define el putchar('\n')

using namespace std;
const double eps = 1e-15, pi = 3.1415926535897932385;
typedef long long LL;
typedef pair<int,int> Pr;
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1}, inf = 0x7fffffff;
//Author : SharpnessV
//#define main Solution
//char buf[1<<22],*p1=buf,*p2=buf;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int read(){
    int x = 0;bool f = 1;char ch = gc();
    while(!isdigit(ch))f = ('-' == ch ? 0 : 1), ch = gc();
    while(isdigit(ch))x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc();
    if(f)return x;return -x;
}
inline LL Read(){
    LL x = 0;bool f = 1;char ch = gc();
    while(!isdigit(ch))f = ('-' == ch ? 0 : 1), ch = gc();
    while(isdigit(ch))x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc();
    if(f)return x;return -x;
}
int gcd(int x,int y){return y ? gcd(y, x % y) : x;}
int lcm(int x,int y){return x / gcd(x, y) * y;}
#define P 1000000007
//#define P 998244353
#define bas 229
inline void ad(int &x, int y){x += y; if(x >= P) x -= P;}
inline void su(int &x, int y){x -= y; if(x < 0) x += P;}
inline void cmn(int &x,int y){if(y < x) x = y;}
inline void cmx(int &x,int y){if(y > x) x = y;}
inline void cmn(LL &x, LL y){if(y < x) x = y;}
inline void cmx(LL &x, LL y){if(y > x) x = y;}

int Pow(int x, int y){
	if(y < 0)return Pow(Pow(x, P - 2), -y);
	int now = 1 ;
	for(;y;y >>= 1, x = 1LL * x * x % P)if(y & 1) now = 1LL * now * x % P;
	return now;
}

/*******************************************************************************************************************/
/*                                                                                                                 */
/*******************************************************************************************************************/

#define N 105

int n, m, k, f[N][1 << 10], v[N];
vector<Pr>e[N];
priority_queue<Pr>q;
void dij(int s){
	while(!q.empty())q.pop();
	rp(i, n)q.push(mp(-f[i][s], i));
	memset(v, 0, sizeof(v));
	while(!q.empty()){
		int x = q.top().se;
		q.pop(), v[x] = 1;
		go(y, e[x])if(f[x][s] + y.se < f[y.fi][s])
			f[y.fi][s] = f[x][s] + y.se, q.push(mp(-f[y.fi][s], y.fi));
		while(!q.empty() && v[q.top().se])q.pop();
	}
}
int main(){
	//int T = read();while(T--)solve();
	n = read(), m = read(), k = read();
	rp(i, m){
		int x = read(), y = read(), z = read();
		e[x].pb(mp(y, z)), e[y].pb(mp(x, z));
	}
	memset(f, 0x3f, sizeof(f));
	rp(i, k){
		int x = read();
		f[x][1 << (i - 1)] = 0;
	}
	rp(i, (1 << k) - 1){
		rp(x, n)
			for(int j = (i - 1) & i; j ;j = (j - 1) & i)cmn(f[x][i], f[x][j] + f[x][i ^ j]);
		dij(i);
	}
	int ans = inf;
	rp(i, n)cmn(ans, f[i][(1 << k) - 1]);
	printf("%d\n", ans);
	return 0;
}

这篇关于【模板】最小斯坦纳树的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！