题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1808

题目分类：动态规划

题意：

给出一个树和一些额外的边，删去权值最小的边使得图中没有偶环，树边不能删除。

题解：

逆向思维

将问题变成给出一棵树和一些边，加入权值最多的边使得不出现偶环。

为了使得图中没有偶环，首先不能加入链接两个距离为奇数的点的边

同时每一条树边不能被非树边覆盖两次。

转化为给定一棵树和一些边球最大生成仙人掌

可以从每个点的度数不超过10入手，状态压缩dp[i][mask]表示在第i个点上i的儿子中被删除的点是mask

详情参见ioi2007题解

程序：

#include<cstdio>
#include<algorithm>
using namespace std;
struct node
{
	long long u,v,va,lca;
}e[60000];
long long fat[60000];
struct nod
{
	long long to,next;
}g[60000];
long long ed,st[60000],tim,deg[60000],wei[60000],col[60000],finish[60000],dp[1500][1500];
long long dep[60000],n,m,x1,x2,x3,tot;
inline void add(long long x,long long y)
{
	ed++;
	g[ed].to=y;
	g[ed].next=st[x];
	st[x]=ed;
}
inline void dfs(long long x)
{
	tim++;
	for (long long i=st[x];i!=0;i=g[i].next)
	{
		if(g[i].to!=fat[x])
		{
			fat[g[i].to]=x;
			wei[g[i].to]=(1<<deg[x]);
			col[g[i].to]=(col[x]^1);
			dep[g[i].to]=dep[x]+1;
			deg[x]++;
			dfs(g[i].to);
		}
	}
	tim++;
	finish[x]=tim;
}
inline void getlca(long long x)
{
	long long u=e[x].u;
	long long v=e[x].v;
	while (dep[u]>dep[v])u=fat[u];
	while (dep[v]>dep[u])v=fat[v];
	while (u!=v)
	{
		u=fat[u];
		v=fat[v];
	}e[x].lca=v;
	//printf("%I64d %I64d\n",x,v);
}
inline bool cmp(node x,node y)
{
	return finish[x.lca]<finish[y.lca];
}int tx=100;
inline void solve()
{
	for (long long i=1;i<=m;i++)
	{
		if(col[e[i].u]!=col[e[i].v]&&e[i].va!=0)continue;
		long long u=e[i].u,cu=0;
		long long v=e[i].v,cv=0;
		long long ss=e[i].va;//if(i<=tx)printf("%I64d %I64d %I64d---------------------------%I64d\n",u,v,e[i].lca,i);
		while (u!=e[i].lca)
		{//if(i<=tx)printf("%I64d %I64d %I64d\n",u,cu,ss);
			ss+=dp[u][cu];
			cu=wei[u];
			u=fat[u];
		}
		while (v!=e[i].lca)
		{//if(i<=tx)printf("%I64d %I64d %I64d\n",v,cv,ss);
			ss+=dp[v][cv];
			cv=wei[v];
			v=fat[v];
		}
		for (long long mask=((1<<deg[e[i].lca])-1);mask>=0;mask--)
		{
			if(!((mask&cv)||(mask&cu)))
			{
				dp[e[i].lca][mask]=max(dp[e[i].lca][mask],ss+dp[e[i].lca][mask|cv|cu]);
			}
		}
	}
}
int main()
{
//	freopen("training.in","r",stdin);
//	freopen("training.out","w",stdout);
	scanf("%lld %lld",&n,&m);
	for (long long i=1;i<=m;i++)
	{
		scanf("%lld %lld %lld",&x1,&x2,&x3);
		tot+=x3;
		e[i].u=x1;
		e[i].v=x2;
		e[i].va=x3;
		if(x3==0)add(x1,x2),add(x2,x1);
	}
	dfs(1);
	for (long long i=1;i<=m;i++)
	{
		getlca(i);
	}
	sort(e+1,e+m+1,cmp);
	solve();
	printf("%lld\n",tot-dp[1][0]);
	return 0;
}