难得自己想出来一道 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;
}
标签:连通,ch,int,题解,fa,read,Roads,100,CF1149D
From: https://www.cnblogs.com/zcr-blog/p/16912925.html