bzoj1402 Ticket to Ride 斯坦纳树 + 状压dp

给定\(n\)个点，\(m\)条边的带权无向图

选出一些边，使得\(4\)对点之间可达，询问权值最小为多少

\(n \leqslant 30, m \leqslant 1000\)

---

首先看数据范围，\(4\)对点，也就是\(8\)个点，很小

上斯坦纳树（局部最小生成树）

然而好像题目并不是斯坦纳树，可能是一些树拼到一起

那么就再做一个状压\(dp\)即可

复杂度\(O(3^8 * n + 2^8 * nm + 2^{12} * n)\)

---

#include <map>

#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

const int sid = 55;

const int eid = (1 << 9) - 1;

inline void cmin(int &a, int b) { if(a > b) a = b; }

int n, m, nc;

int U[sid], V[sid], cl[sid], ip[sid];

int f[sid][eid], E[sid][sid];

string s[55], sa, sb;

map <string, int> id;

int inq[sid];

queue <int> q;

void spfa(int S) {

	memset(inq, 0, sizeof(inq));

	for(int i = 1; i <= n; i ++) q.push(i);

	while(!q.empty()) {

		int id = q.front(); q.pop(); inq[id] = 0;

		for(int j = 1; j <= n; j ++)

			if(f[j][S] > f[id][S] + E[id][j]) {

				f[j][S] = f[id][S] + E[id][j];

				if(!inq[j]) q.push(j), inq[j] = 1;

			}

	}

}

void wish1() {

	memset(f, 56, sizeof(f));

	for(int i = 1; i <= n; i ++)

		if(cl[i]) {

			nc ++;

			ip[i] = nc;

			f[i][(1 << nc - 1)] = 0;

		}

	for(int S = 0; S <= (1 << nc) - 1; S ++) {

		for(int i = 1; i <= n; i ++)

			for(int T = S; T; T = (T - 1) & S)

				cmin(f[i][S], f[i][T] + f[i][S ^ T]);

		spfa(S);

	}

}

int g[eid];

void wish2() {

	memset(g, 56, sizeof(g)); g[0] = 0;

	for(int s = 0; s <= (1 << 4) - 1; s ++)

	for(int i = 1; i <= n; i ++)

	for(int S = 0; S <= (1 << nc) - 1; S ++) {

		int T = 0;

		for(int k = 1; k <= 4; k ++)

			if((S & (1 << ip[U[k]] - 1)) && (S & (1 << ip[V[k]] - 1)))

				T |= (1 << k - 1);

		cmin(g[s | T], g[s] + f[i][S]);

	}

	printf("%d\n", g[(1 << 4) - 1]);

}

int main() {

	freopen("bzoj1402.in", "r", stdin);

	freopen("bzoj1402.out", "w", stdout);

	cin >> n >> m;

	for(int i = 1; i <= n; i ++) {

		cin >> s[i];

		id[s[i]] = i;

	}

	memset(E, 56, sizeof(E));

	for(int i = 1; i <= m; i ++) {

		int u, v, w;

		cin >> sa >> sb >> w;

		u = id[sa]; v = id[sb];

		cmin(E[u][v], w); E[v][u] = E[u][v];

	}

	for(int i = 1; i <= 4; i ++) {

		int u, v;

		cin >> sa >> sb;

		u = id[sa]; v = id[sb];

		U[i] = u; V[i] = v;

		cl[u] = cl[v] = 1;

	}

	wish1(); wish2();

	return 0;

}