Run

题意:

给出一张图(点数为n,边数为m)的一个生成树和一些非树边。

每条非树边有一个代价w，表示炸毁这条边需要付出的代价。

求炸毁一些非树边使得图中不存在偶环所付出的最小代价。

特别地，生成树上点的度数不超过10.

数据范围:n<=1000,m<=4000

分析:

首先如果一条非树边跨越了树上奇数条边，则这条边必须炸毁。

剩下的边，如果任意两条边所跨越的树上路径有公共边，则会存在偶环。

考虑到每个节点的儿子最多只有10个，我们可以考虑状压dp.

令f[x][s]表示以x为根的子树,只考虑集合s中儿子时能保留的边的最大权值。

令g[x][i]表示以x为根的子树,不考虑x的第i个儿子时能保留的边的最大权值。

每条非树边，只在它的端点的lca处考虑影响。

为了让路径不重复，则该非树边所覆盖的路径都不能被选。

暴力从一个端点到lca统计不考虑路径上的边时的最大权值。

再与该非树边没有覆盖的部分一起更新答案。

复杂度O(n*2¹⁰+n*m)

#include <vector>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

#define g() getchar()
template<class Q>void Scan(Q&x){
	char c;int f=1;
	while(c=g(),c<48||c>57)if(c=='-')f=-1;
	for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
	x*=f;
}

#define Max(x,y) if(x<y)x=y
#define Min(x,y) if(x>y)x=y 
#define pb push_back
#define rep(i,a,b) for(int i=a;i<b;++i)

const int MAXN=1005;
const int MAXS=1<<10;

int n,m;

struct edge{
	int t,n;
	edge(int t=0,int n=0):t(t),n(n){}
}e[MAXN<<1];
int head[MAXN],tot;
inline void AddEdge(int s,int t){
	e[++tot]=edge(t,head[s]),head[s]=tot;
	e[++tot]=edge(s,head[t]),head[t]=tot;
}

int p[MAXN],dep[MAXN];

vector<int>ch[MAXN],qy[MAXN];

void dfs(int x){
	for(int i=head[x],y;i;i=e[i].n)
		if((y=e[i].t)!=p[x]){
			p[y]=x;
			dep[y]=dep[x]+1;
			ch[x].pb(y);
			dfs(y);
		}
}

inline int lca(int x,int y){
	if(dep[x]>dep[y])swap(x,y);
	while(dep[y]>dep[x])y=p[y];
	while(p[x]!=p[y])x=p[x],y=p[y];
	return x==y?x:p[x];
}

struct edge1{
	int u,v,w;
	inline void scan(){
		Scan(u),Scan(v),Scan(w);
	}
}tmp[MAXN*5];

int ans;

inline void Init(){
	Scan(n),Scan(m);
	rep(i,1,m+1){
		tmp[i].scan();
		ans+=tmp[i].w;
		if(!tmp[i].w){
			AddEdge(tmp[i].u,tmp[i].v);
		}
	}
	dfs(1);
	rep(i,1,m+1){
		if(!tmp[i].w)continue;
		int u=tmp[i].u,v=tmp[i].v;
		int Lca=lca(u,v);
		if((dep[u]+dep[v]-dep[Lca]*2)&1)continue;
		qy[Lca].pb(i);
	}
}

int dp[MAXN];

int f[MAXN][MAXS],g[MAXN][10];

inline int swim(int x,int par,int&res){
	int ban=-1;
	while(x!=par){
		if(~ban)res+=g[x][ban];
		else res+=dp[x];
		int s=ch[p[x]].size();
		rep(i,0,s)
			if(x==ch[p[x]][i]){
				ban=i; break;
			} 
		x=p[x];
	}
	return ban;
}

void tree_dp(int x){
	for(int i=head[x],y;i;i=e[i].n)
		if((y=e[i].t)!=p[x])tree_dp(y);
	int s=ch[x].size();
	int maxs=1<<s;
	rep(set,0,maxs){
		int res=0;
		rep(i,0,s)
			if(set>>i&1){
				res+=dp[ch[x][i]];
			}
		Max(f[x][set],res);
	}
	int c=qy[x].size();
	rep(i,0,c){
		int u=tmp[qy[x][i]].u;
		int v=tmp[qy[x][i]].v;
		int res=tmp[qy[x][i]].w;
		int bu=max(0,1<<swim(u,x,res));
		int bv=max(0,1<<swim(v,x,res));
		rep(set,0,maxs){
			if(bu&&(set&bu)==bu||bv&&(set&bv)==bv)
				continue;
			int ns=set^bu^bv;
			Max(f[x][ns],res+f[x][set]);
		}
	}
	rep(set,0,maxs){
		rep(i,0,s)
			if(!(set>>i&1)){
				Max(g[x][i],f[x][set]);
			}
		Max(dp[x],f[x][set]);
	}
}

inline void Solve(){
	tree_dp(1);
	ans-=dp[1];
	printf("%d\n",ans);
}

int main(){
	freopen("run.in","r",stdin);
	freopen("run.out","w",stdout);
	Init(); Solve(); return 0;
}