自动搬运

查看原文

来自洛谷，原作者为

	LPF 看不懂黑白却听得到钟摆，去新世界冒险和内心作伴

搬运于2025-08-24 22:17:15，当前版本为作者最后更新于2021-07-17 20:38:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

状压好题，希望写的足够详细。

吃货 JYY

给定一张图，有一些必经边，求从 $1$ 出发，经过每条必经边至少一遍，最后回到 $1$ 的最短距离。

首先他的旅行过程在最优情况下是一定是一条欧拉回路，而欧拉回路存在的充要条件是：

1. 图连通。
2. 所有点的度数都为偶数。

必经边必选，相当于需要在必经边的基础上不断加边，使图连通且所有点的度数均为偶数。

然后看到数据范围 $n\leq 13$ 不难想到状压，关键是既满足图连通又满足度数为偶数这不太好处理。

考虑一个简化问题：

给出一张图和任意两点间的最短路，求将图改造为欧拉图需要加的最小边权和。

可以证明如果一张连通图不是欧拉图，那么它的奇点个数为偶数。

那么我们需要的是让每对奇点两两连接最短路，显然这样就可以使它们变成偶点，并且不影响其它点的度数的奇偶性。

这显然可以直接状压，设 $f(S)$ 表示奇点集合为 $S$ 的最小代价，然后每次枚举两个不在集合中的奇点加入即可。

时间 $O(2^n\times n^2)$，不排除通过枚举子集等方法进一步优化的可能，不过这也够了。

现在回到原问题，我们想要运用上面的方法，首先需要处理出任意两点间的最短路，这个可以预先 Floyd。

然后是给出一个连通图的每个点的奇偶性，当然也要包含点的连通性。

表现在进制上，就至少需要三进制表示了：

1. $0$，表示这个点不与 $1$ 号节点连通。
2. $1$，表示连通并且度数为奇数。
3. $2$，表示连通并且度数为偶数。

至于为什么不需要另外的状态，表示不连通的点的奇偶性，因为这里运用了一个统一计算的思想。

就是当前只考虑非必选边的构图情况，之后再统一加上必经边的影响，也就是说没有连通的点就是没有连边的点，度数一定为 $0$。

同时这样也保证了不会用到 $5$ 维状压这种恐怖的东西。

然后每次转移有两种选择，都是从已连通连通的点 $u$ 出发，扩展到未连通的点 $v$：

1. 沿着某条必经边到达 $v$，$v$ 连通了，但是度数算作 $0$，也不需要增加代价。
2. 沿着某个最短路到达 $v$，$v$ 连通了且度数为 $1$，$u$ 的度数奇偶性也发生变化，代价加上最短路的距离。

但是可以发现，状态间的转移没有固定的方向，因为度数由偶变奇时，在宏观意义上相当于数变小，而由奇变偶则相反。

所以可以利用 SPFA 的思想反复迭代，直到无法更新，显然保证了正确性。

然后再利用上面的方法就可以结合出答案了，不要忘记加上必经边对 点的度数的奇偶性 和 总代价 的影响。

总时间复杂度大约为 $O(3^nn^2)$，需要考虑利用 SPFA 收束带来的常数影响。（不过好像可以证明只会收束一次？）

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

#define X first
#define Y second 
#define MP make_pair
typedef pair<int, int> PII;
const int N = 15, M = 2000010;
const int INF = 0x3f3f3f3f;

int n, k, m, P[N], deg[N], dis[N][N], f[1 << N], g[M];
bool vis[M];
vector<PII> G[N];

int read(){
	int x = 0, f = 1; char c = getchar();
	while(c < '0' || c > '9') f = (c == '-') ? -1 : 1, c = getchar();
	while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
	return x * f;
}

void Pre_Work(){
	memset(dis, 0x3f, sizeof(dis));
	for(int i = 1; i <= n; i ++) dis[i][i] = 0;
	P[0] = 1;
	for(int i = 1; i <= n; i ++) P[i] = P[i - 1] * 3;
}

void Get_Map(){
	memset(g, 0x3f, sizeof(g)); g[2] = 0;
	queue<int> q; q.push(2);
	while(!q.empty()){
		int s = q.front(); q.pop();
		vis[s] = false;
		
		for(int u = 0; u < n; u ++) if((s / P[u]) % 3 > 0)
		for(int i = 0; i < (int) G[u].size(); i ++){
			int v = G[u][i].X;
			if((s / P[v]) % 3 == 0){
				int t = s + P[v] * 2;
				if(g[t] > g[s]){
					g[t] = g[s];
					if(!vis[t]) q.push(t), vis[t] = true;
				}
			}
		}
		
		for(int u = 0; u < n; u ++) if((s / P[u]) % 3 > 0)
			for(int v = 0; v < n; v ++) if((s / P[v]) % 3 == 0){
				int t = s + P[v];
				t += ((s / P[u]) % 3 == 1) ? P[u] : - P[u];
				if(g[t] > g[s] + dis[u][v]){
					g[t] = g[s] + dis[u][v];
					if(!vis[t]) q.push(t), vis[t] = true;
				}
			}
	}
}

void Get_Dis(){
	memset(f, 0x3f, sizeof(f));
	f[0] = 0;
	for(int s = 0; s < (1 << n); s ++)
		for(int u = 0; u < n; u ++) if(!(s >> u & 1))
			for(int v = u + 1; v < n; v ++) if(!(s >> v & 1)){
				int t = s + (1 << u) + (1 << v);
				f[t] = min(f[t], f[s] + dis[u][v]);
			}
}

int main(){
	n = read(), k = read();
	Pre_Work(); int sum = 0;
	for(int i = 1; i <= k; i ++){
		int u = read() - 1, v = read() - 1, w = read();
		G[u].push_back(MP(v, w));
		G[v].push_back(MP(u, w));
		dis[u][v] = dis[v][u] = min(dis[u][v], w);
		deg[u] ++, deg[v] ++; sum += w;
	}
	m = read();
	for(int i = 1; i <= m; i ++){
		int u = read() - 1, v = read() - 1, w = read();
		dis[u][v] = dis[v][u] = min(dis[u][v], w);
	}
	
	for(int k = 0; k < n; k ++)
		for(int i = 0; i < n; i ++) if(dis[i][k] != INF)
			for(int j = 0; j < n; j ++) if(dis[k][j] != INF)
				dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
	
	Get_Map(); Get_Dis();
	
	int ans = INF;
	for(int i = 0; i < P[n]; i ++){
		int s = i;
		bool flag = false;
		for(int u = 0; u < n; u ++)
			if(G[u].size() && !((s / P[u]) % 3)) {flag = true; break;}
		if(flag) continue;
		for(int u = 0; u < n; u ++)
			if(deg[u] & 1) s += ((i / P[u]) % 3 == 1) ? P[u] : - P[u];
		int t = 0;
		for(int u = 0; u < n; u ++)
			if((s / P[u]) % 3 == 1) t += (1 << u);
		ans = min(ans, g[i] + f[t]);
	}
	printf("%d\n", ans + sum);
	return 0;
}