[题解] CF1149D Abandoning Roads

难得自己想出来一道 3000 分的题，虽然说考试的时候打挂了…

首先先对较小的边缩点，然后求连通块内的最短路。显然，连通块内其实想怎么走就怎么走，但不能走较大的边。然后不同连通块用较大的边连起来，就完事了？你发现较大的边走起来必须是一条链，也就是不能回到之前存在过连通块，比如说 \(1\to 2\to 3\to 4\) 边权都是 \(3\)，而 \(1\to 5\to 4\) 的边权都是 \(4\)，这时走外面一圈会更短但是这不符合条件。所以我们有一个暴力的思路，状压连通块。连通块的个数是 \(O(n)\) 的，仔细观察数据范围 \(n\le 70\)。然后发现只有一个点的连通块显然不用压，只有两个的也显然不用压，于是就只有 \(70/3=23\) 个连通块。还是太多，观察三个点的连通块，由于 \(a<b\)，所以其实也一定不会走出去再走回来，所以也不用压，于是要压的点只有 \(70/4=17\) 个了。然后跑最短路转移（类似最小斯坦纳树）即可。复杂度 \(O(2^{n/4}m\log m)\)。

#include <bits/stdc++.h>
#define pii pair<int, int>
#define MP make_pair
#define fi first
#define se second
using namespace std;
template <typename T>
void read(T &x) {
	T sgn = 1;
	char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1;
	for (x = 0; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
	x *= sgn;
}
int n, m, A, B, fa[100];
int dis[100][100];
bool vis[100];
vector<int> vec[100];
int sz[100];
int stk[100], top, id[100];
int f[1 << 18][75];
int g[75][75];
queue<int> q;
priority_queue<pii, vector<pii>, greater<pii>> qq; 
int Find(int x) {
	return fa[x] == x ? x : fa[x] = Find(fa[x]);
}
int main() {
	read(n); read(m); read(A); read(B);
	if (A > B) swap(A, B);
	for (int i = 1; i <= n; i++) fa[i] = i;
	for (int i = 1, u, v, w; i <= m; i++) {
		read(u); read(v); read(w);
		if (w == A) vec[u].push_back(v), vec[v].push_back(u);
		else g[u][v] = g[v][u] = B;
		if (w == A && Find(u) != Find(v)) {
			fa[Find(u)] = Find(v);
		}
	}
	for (int i = 1; i <= n; i++) Find(i);
	for (int i = 1; i <= n; i++) {
		q.push(i);
		for (int j = 1; j <= n; j++) {
			vis[j] = 0;
			dis[i][j] = -1;
		}
		vis[i] = 1; dis[i][i] = 0;
		while (q.size()) {
			int u = q.front();
			q.pop(); 
			for (int v : vec[u]) {
				if (!vis[v]) {
					dis[i][v] = dis[i][u] + 1;
					q.push(v);
					vis[v] = 1;
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) sz[fa[i]]++;
	for (int i = 1; i <= n; i++) if (fa[i] == i && sz[i] >= 4) {
		stk[id[i] = top++] = i;
	}
	memset(f, 0x3f, sizeof(f));
	if (sz[fa[1]] < 4) {
		f[0][1] = 0;
	} else {
		f[1 << id[fa[1]]][1] = 0;
	}
	for (int s = 0; s < (1 << top); s++) {
		while (qq.size()) qq.pop();
		for (int i = 1; i <= n; i++) if (f[s][i] < 0x3f3f3f3f) {
			qq.push(MP(f[s][i], i));
		}
		for (int i = 1; i <= n; i++) vis[i] = 0;
		while (qq.size()) {
			int u = qq.top().se; qq.pop();
			if (vis[u]) continue;
			vis[u] = 1;
			for (int v = 1; v <= n; v++) {
				if (fa[u] == fa[v]) {
					if (f[s][v] > f[s][u] + dis[u][v] * A) {
						f[s][v] = f[s][u] + dis[u][v] * A;
						qq.push(MP(f[s][v], v));
					}
				} else {
					if (!g[u][v]) continue;
					if (sz[fa[v]] < 4) {
						if (f[s][v] > f[s][u] + g[u][v]) {
							f[s][v] = f[s][u] + g[u][v];
							qq.push(MP(f[s][v], v));
						}
					}
				}
			}
		}
		for (int i = 1; i <= n; i++) {
			if (sz[fa[i]] >= 4) {
				if (s & (1 << id[fa[i]])) continue;
				int t = s | (1 << id[fa[i]]);
				for (int j = 1; j <= n; j++) if (f[s][j] < 0x3f3f3f3f && fa[i] != fa[j] && g[j][i]) {
					f[t][i] = min(f[t][i], f[s][j] + g[j][i]);
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		int ans = 0x3f3f3f3f;
		for (int s = 0; s < (1 << top); s++) {
			ans = min(ans, f[s][i]);
		}
		printf("%d ", ans);
	}
	return 0;
}

原文地址：http://www.cnblogs.com/zcr-blog/p/16912925.html