如果小地图存在欧拉回路，那么对于大地图的每条边，都可以恰好走两次使得小地图每条边恰好经过一次，令$sum$为小地图的边权和，则此时答案为$m\times sum$。
否则小地图存在欧拉路径，找到两个奇点$A$和$B$，那么最优解中大地图每条边一定经过$1$次或者$2$次，且仅保留经过$1$次的边后大地图里每个点度数都是$0$。
令$d[i][j]$为小地图中$i$到$j$的最短路，若要从$i$到$j$走一次，那么最优方案是把$i,j,A,B$这$4$个点用最短路配成两对，牺牲掉这两条最短路；若要从$i$到$j$走两次，那么最优方案牺牲掉$A,B$的最短路。
注意到$m\leq n+5$，所以取大地图的一棵生成树，然后$2^{m-n+1}$暴力枚举非树边的经过次数，那么每条树边的经过次数可以从下而上递推得到。
时间复杂度$O(p^3+n2^{n-m+1})$。
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=10010,M=205;
const ll inf=1LL<<60;
int n,m,ce,P,Q,A,B,i,j,k,x,y,z,S,at[N],f[N],e[N][2],deg[N];ll d[M][M],sum,ans,base;
int g[N],v[N<<1],nxt[N<<1],ed,q[N],cnt;ll w1[N],w2[N];
int F(int x){return f[x]==x?x:f[x]=F(f[x]);}
inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}
inline void up(ll&a,ll b){a>b?(a=b):0;}
inline ll ask1(int x,int y){
x=at[x],y=at[y];
return max(max(sum-d[A][x]-d[B][y],sum-d[A][y]-d[B][x]),sum-d[x][y]-d[A][B]);
}
inline ll ask2(int x,int y){return sum-d[A][B];}
void dfs(int x,int y){
f[q[++cnt]=x]=y;
if(y)w1[x]=ask1(x,y),w2[x]=ask2(x,y);
for(int i=g[x];i;i=nxt[i])if(v[i]!=y)dfs(v[i],x);
}
int main(){
scanf("%d%d%d%d",&n,&m,&P,&Q);
for(i=1;i<=n;i++)scanf("%d",&at[i]);
for(i=1;i<=n;i++)f[i]=i;
for(i=1;i<=m;i++){
scanf("%d%d",&x,&y);
if(F(x)!=F(y))f[f[x]]=f[y],add(x,y),add(y,x);
else{
e[ce][0]=x;
e[ce++][1]=y;
}
}
for(i=1;i<=P;i++)for(j=1;j<=P;j++)d[i][j]=i==j?0:inf;
while(Q--){
scanf("%d%d%d",&x,&y,&z);
deg[x]^=1,deg[y]^=1,sum+=z;
d[x][y]=d[y][x]=z;
}
for(i=1;i<=P;i++)if(deg[i]){
if(!A)A=i;
else B=i;
}
if(!A)return printf("%lld",sum*m),0;
for(k=1;k<=P;k++)for(i=1;i<=P;i++)for(j=1;j<=P;j++)up(d[i][j],d[i][k]+d[k][j]);
dfs(1,0);
for(S=0;S<1<<ce;S++){
base=0;
for(i=1;i<=n;i++)deg[i]=0;
for(i=0;i<ce;i++){
x=e[i][0],y=e[i][1];
if(S>>i&1)deg[x]^=1,deg[y]^=1,base+=ask1(x,y);else base+=ask2(x,y);
}
for(i=n;i>1;i--){
x=q[i];
if(deg[x])deg[f[x]]^=1,base+=w1[x];else base+=w2[x];
}
ans=max(ans,base);
}
return printf("%lld",ans),0;
}
原文：https://www.cnblogs.com/clrs97/p/12162797.html