description
给一张(n)点(m)条边的带权图，保证无重边无自环，并给出这张图的一棵生成树。你可以任意修改每条边的边权，但是要求修改后边权仍是整数。修改的代价定义为边权的变化量。你需要保证边权修改后给出的生成树是原图的最小生成树（可以不唯一）。
求最小修改代价。
(nle50,mle800)。
sol
其实做这道题的原因是今天打百度之星的时候发现自己并不会KM
首先很显然，树边的边权只可能减小，非树边的边权只可能增大。
设每条边的修改量为(d_i)，我们考虑每一条非树边(i)，对于它覆盖到的每一条树边(j)，我们要求修改后(i)的边权不小于(j)的边权，也就是(w_j+d_j ge w_i-d_i)，移项后(d_i+d_j ge w_i-w_j)。
这个东西就是(KM)顶表的要求。所以直接跑(KM)就可以了。复杂度可以做到(O(nm^2))
code
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int gi(){
int x=0,w=1;char ch=getchar();
while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if (ch=='-') w=0,ch=getchar();
while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return w?x:-x;
}
const int N = 1005;
const int inf = 1<<30;
struct edge{int u,v,w;}E[N];
int n,m,to[N],nxt[N],ww[N],head[N],cnt=1,fa[N],dep[N],ref[N],a[N][N],tot;
int slack[N],lv[N],rv[N],mat[N],vis[N],pre[N];
void link(int u,int v,int w){
to[++cnt]=v;nxt[cnt]=head[u];ww[cnt]=w;head[u]=cnt;
}
void dfs(int u,int f){
fa[u]=f;dep[u]=dep[f]+1;
for (int e=head[u];e;e=nxt[e])
if (to[e]!=f) ref[to[e]]=e>>1,dfs(to[e],u);
}
void aug(int s){
for (int i=0;i<=tot;++i) slack[i]=inf,vis[i]=pre[i]=0;
int u=0;mat[u]=s;
do{
int now=mat[u],d=inf,nxt;vis[u]=1;
for (int v=1;v<=tot;++v)
if (!vis[v]){
if (lv[now]+rv[v]-a[now][v]<slack[v])
slack[v]=lv[now]+rv[v]-a[now][v],pre[v]=u;
if (d>slack[v]) d=slack[v],nxt=v;
}
for (int i=0;i<=tot;++i)
if (vis[i]) lv[mat[i]]-=d,rv[i]+=d;
else slack[i]-=d;
u=nxt;
}while (mat[u]);
while (u) mat[u]=mat[pre[u]],u=pre[u];
}
int main(){
freopen("1937.in","r",stdin);
freopen("1937.out","w",stdout);
n=gi();m=gi();tot=max(n-1,m-n+1);
for (int i=1;i<=m;++i){
E[i]=(edge){gi(),gi(),gi()};
if (E[i].u>E[i].v) swap(E[i].u,E[i].v);
}
for (int i=1;i<n;++i){
int u=gi(),v=gi(),w;if (u>v) swap(u,v);
for (int j=1;j<=m;++j)
if (E[j].u==u&&E[j].v==v){
w=E[j].w;vis[j]=1;break;
}
link(u,v,w);link(v,u,w);
}
dfs(1,0);
for (int i=1,num=0;i<=m;++i)
if (!vis[i]){
int u=E[i].u,v=E[i].v;++num;
while (u^v){
if (dep[u]<dep[v]) swap(u,v);
int e=ref[u];a[e][num]=ww[e<<1]-E[i].w;
u=fa[u];
}
}
for (int i=1;i<=tot;++i)
for (int j=1;j<=tot;++j)
lv[i]=max(lv[i],a[i][j]);
for (int i=1;i<n;++i) aug(i);
int ans=0;
for (int i=1;i<=tot;++i) ans+=lv[i]+rv[i];
printf("%d
",ans);
return 0;
}