好像很久没有写blog了的样子。。而且好像之前写的都是水题。。
既然这样。。那就继续写水题吧！23333..........
这道题可以用费用流或者KM来搞
显然是减非树边 加树边
由于是最小生成树 所以一个非树边x->y要比树上此路径上的所有边要短
所以要满足w[i]-delta[i]<=w[j]+delta[j]，移项后得w[i]-w[j]<=delta[i]+delta[j]
然后就可以愉快地搞了、、
莫名作死打了个KM 感觉又长又慢起码相比费用流是这样的
当然了我的KM还是挺快的 56ms（KM的复杂度就是玄学。。）就是代码挺丑
#include<bits/stdc++.h> using namespace std; const int N=52,M=1010,inf=1e9+7; inline int read() { char ch=getchar(); int x=0,f=1; while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} return x*f; } struct node{int x,y,c,next,id;bool v;}a[M],e[M*2]; int len,first[N]; void ins(int x,int y,int c,int id) { e[++len]=(node){x,y,c,first[x],id},first[x]=len; } int n,m,id[N][N],dep[N],fa[N][10],ups[N],vx[M],vy[M]; int slack[M],lx[M],ly[M],w[M][M],xm[M],ym[M],pre[M],t; bool vis[N]; void dfs(int x) { vis[x]=1; for(int k=first[x];k;k=e[k].next) { int y=e[k].y; if(!vis[y]) { fa[y][0]=x; dep[y]=dep[x]+1; ups[y]=e[k].id; dfs(y); } } } int lca(int x,int y) { if(dep[x]<dep[y])x^=y^=x^=y; for(int i=8;i>=0;i--)if(dep[x]-dep[y]>=(1<<i))x=fa[x][i]; if(x==y)return x; for(int i=8;i>=0;i--) if(dep[x]>(1<<i) && fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i]; return fa[x][0]; } void bt(int x,int p,int k) { while(x!=p) { w[ups[x]][k]=max(0,a[ups[x]].c-a[k].c); x=fa[x][0]; } } void go(int y) { for(int x,z;y;y=z) { x=pre[y],z=xm[x]; xm[x]=y,ym[y]=x; } } void KM(int x) { for(int i=1;i<=m;i++)slack[i]=inf; t++; queue<int>q; q.push(x); vx[x]=t; while(1) { while(!q.empty()) { x=q.front(); q.pop(); for(int y=1;y<=m;y++)if(vy[y]!=t) { if(lx[x]+ly[y]==w[x][y]) { pre[y]=x; if(!ym[y]){go(y);return;} q.push(ym[y]); vx[ym[y]]=t,vy[y]=t; } else if(slack[y]>lx[x]+ly[y]-w[x][y]) slack[y]=lx[x]+ly[y]-w[x][y],pre[y]=x; } } int de=(1<<30); for(int y=1;y<=m;y++)if(vy[y]!=t)de=min(de,slack[y]); for(int i=1;i<=m;i++) { if(vx[i]==t)lx[i]-=de; if(vy[i]==t)ly[i]+=de; else slack[i]-=de; } for(int y=1;y<=m;y++)if(vy[y]!=t && !slack[y]) { if(!ym[y]){go(y);return;} q.push(ym[y]); vx[ym[y]]=t,vy[y]=t; } } } int main() { int i,j,x,y,c; n=read(),m=read(); for(i=1;i<=m;i++) { x=read(),y=read(),c=read(); if(x>y)x^=y^=x^=y; a[i].x=x,a[i].y=y,a[i].c=c; id[x][y]=i; } for(i=1;i<n;i++) { x=read(),y=read(); if(x>y)x^=y^=x^=y; ins(x,y,a[id[x][y]].c,id[x][y]); ins(y,x,a[id[x][y]].c,id[x][y]); a[id[x][y]].v=1; } dep[1]=1; dfs(1); for(j=1;j<=8;j++)for(i=1;i<=n;i++)fa[i][j]=fa[fa[i][j-1]][j-1]; for(i=1;i<=m;i++)if(!a[i].v) { int l=lca(a[i].x,a[i].y); bt(a[i].x,l,i),bt(a[i].y,l,i); } for(i=1;i<=m;i++)for(j=1;j<=m;j++)lx[i]=max(lx[i],w[i][j]); for(i=1;i<=m;i++)KM(i); int ans=0; for(i=1;i<=m;i++)if(a[i].v)ans+=lx[i]; else ans+=ly[i]; printf("%d\n",ans); return 0; }