题意概述
给定 $n$ 个点 $m$ 条边的无向图，你需要删掉一些边，使得此图没有长度为偶数的简单环。
删掉第 $i$ 条边有 $C_i$ 的花费，有些边又是不能删的。不能删的边形成图的一棵生成树。
$n\leq 1000,m \leq 5000$，点的度数不超过 10。
思路
对于所有非树边，如果非树边所连接的两个点在树上的距离为奇数，那么会构成一个偶环，删去这些边。
考虑两个仅含有一条非树边的奇环，如果他们在树上的部分有交，那么把两个环合并在一起再去掉那些重复的部分剩下的就一定是一个偶环，所以说我们需要留下一张图，使得没有一条边同时属于两个简单环，也就是一个仙人掌（此处没有考虑在最初就被我们删掉的非树边）。容易证明满足上述条件的方案一定合法。
如果让每条非树边覆盖他连接两点树上的路径上的所有边，那么树上的每一条边最多只能被覆盖一次，再将必须删除的最小边权改为总边权-能留下的最大边权。
定义 $f_{(i,S)}$ 为以 $i$ 为根的子树中，不考虑儿子集合 $S$ 的最大边权。
对于一条左右端点$u, v$ 的 $LCA$ 为 $i$ 的非树边，
- 如果不选择，此时的 $f_{(i,S)}=\sum_{son\notin S} f_{(son,0)}$；
-
如果选择这条边，这条边的贡献 $val$ 分为两个部分：
-
$f_{(u,0)} + f_{(v,0)}$
-
对于到 $LCA$ 路径上的的每个点 $p$。设对于 $p$，不包含 $u$ 或 $v$ 的儿子集合为 $K$，贡献为 $\sum f_{(p,K)}$
现在我们可以枚举点 $i$ 的子集 $S$，令子树包含 $u,v$ 的儿子分别为 $x,y$。对于 $\forall S, x\notin S, y\notin S$
$$f_{(i,S)}=\max f_{(i,S|x|y)}+val$$
最终的答案为总边权减去 $f_{(root,0)}$。
时间复杂度 $\Theta (m2^{10}+mn)$。
代码
#include <bits/stdc++.h>
#define max(a,b) (a>b?a:b)
#define pb push_back
#define maxn 1010
#define maxm 5010
struct Edge{
int to,next;
Edge(int a=0,int b=0){
to=a,next=b;
}
}l[maxn<<1];
struct Brid{
int from,to,val;
Brid(int a=0,int b=0,int c=0){
from=a,to=b,val=c;
}
}H[maxm];
int head[maxn],p[maxn][12],cnt,n,m;
int dep[maxn],f[maxn][maxn<<2];
int id[maxn],rid[maxn],tot,sum;
std::vector<int>B[maxn];
void Add(int a=0,int b=0){
l[++cnt]=Edge(b,head[a]);
head[a]=cnt;
}
void Dfs(int u,int fa){
dep[u]=dep[fa]+1;
p[u][0]=fa;
for (register int i=1;i<12;i++)
p[u][i]=p[p[u][i-1]][i-1];
for (register int i=head[u];i;i=l[i].next){
int v=l[i].to;if (v!=fa) Dfs(v,u);
}
}
int Lca(int a,int b){
if (dep[b]<dep[a]) std::swap(a,b);
for (register int i=11;~i;i--)
if (dep[p[b][i]]>=dep[a]) b=p[b][i];
if (a==b) return a;
for (register int i=11;~i;i--)
if (p[a][i]!=p[b][i])
a=p[a][i],b=p[b][i];
return p[a][0];
}
#define fa(i) (p[i][0])
void Solve(int u){
int son=0;
for (register int i=head[u];i;i=l[i].next){
int v=l[i].to;
if (v==fa(u)) continue;
Solve(v);
}
for (register int i=head[u];i;i=l[i].next){
int v=l[i].to;
if (v==fa(u)) continue;
id[son]=v,rid[v]=1<<son,son++;
}
for (register int S=0,tem=0;S<1<<son;++S,tem=0){
for (register int i=0;i<son;i++)
if (!(S>>i&1))
tem+=f[id[i]][0];
f[u][S]=tem;
}
for (register int k=B[u].size()-1;~k;--k){
int i=B[u][k],tem=H[i].val;
if (H[i].from!=u)
tem+=f[H[i].from][0];
if (H[i].to!=u)
tem+=f[H[i].to][0];
int a=0,b=0;
if (H[i].from!=u)
for (a=H[i].from;fa(a)!=u;a=fa(a))
tem+=f[fa(a)][rid[a]];
if (H[i].to!=u)
for (b=H[i].to;fa(b)!=u;b=fa(b))
tem+=f[fa(b)][rid[b]];
for (register int S=0;S<1<<son;++S)
if ((S&rid[a])==0&&(S&rid[b])==0)
f[u][S]=max(f[u][S],f[u][S|rid[a]|rid[b]]+tem);
}
}
#undef fa
int main(){
scanf("%d%d",&n,&m);
for (register int i=1,a,b,c;i<=m;++i){
scanf("%d%d%d",&a,&b,&c);
if (!c) Add(a,b),Add(b,a);
else H[++tot]=Brid(a,b,c),sum+=c;
}
Dfs(1,0);
for (register int i=1;i<=tot;++i){
int t=Lca(H[i].from,H[i].to);
if (!((dep[H[i].from]+dep[H[i].to]-2*dep[t])&1))
B[t].pb(i);
}
Solve(1);
printf("%d",sum-f[1][0]);
return 0;
}