Description
Input
第一行为N、M，其中 表示顶点的数目， 表示边的数目。顶点的编号为1、2、3、……、N-1、N。接下来的M行，每行三个整数Ui，Vi，Wi，表示顶点Ui与Vi之间有一条边，其权值为Wi。所有的边在输入中会且仅会出现一次。再接着N-1行，每行两个整数Xi、Yi，表示顶点Xi与Yi之间的边是T的一条边。
Output
输出最小权值
Sample Input
6 9
1 2 2
1 3 2
2 3 3
3 4 3
1 5 1
2 6 3
4 5 4
4 6 7
5 6 6
1 3
2 3
3 4
4 5
4 6
Sample Output
8
【样例说明】
边(4,6)的权由7修改为3，代价为4
边(1,2)的权由2修改为3，代价为1
边(1,5)的权由1修改为4，代价为3
所以总代价为4+1+3=8
修改方案不唯一
HINT
1<=n<=50,1<=m<=800,1<=wi<=1000
n–>点数..m–>边数..wi—>边权
分析：
我一开始十分simple的想：
我们可以直接在图上作最小生成树，得到一个ans，
实际上这就是我们修改的目标，那我们直接跑一个最小生成树不就行了嘛
然而我忽略了一个条件：
我们可以修改E中的任意一条边
于是我就懵了
实际上，根据贪心的思想，原本在T中的边只减不增，非T边只增不减
而最小生成树又有一个的性质：
对于任意一条树边i和任意一条非树边j，一定有
Wi-di<=Wj+dj (改变后的树边权值一定小于等于任何一条非树边)
看似是一个很zz很显然的结论
但是我们稍微变一下形，就可以得到:di+dj>=Wi-Wj
如果我们把d看做一个函数
那么这和可行顶标的定义是一样的：
可行顶标：
可行顶标是一个节点函数l，使得对于任意的弧(x,y)，都有l(x)+l(y)>=W(x,y)相等子图：
包含原图的所有点，只包含l(x)+l(y)=W(x,y)的边
相等子图的完美匹配就是原图的最大权匹配
也就是说我们只要找到一个可行相等子图，
那么完美匹配的边权和就是di的和
我们把所有边都看成点
X部：非树边
Y部：树边
两部之间的连边是边权差（di+dj>=Wi-Wj( 树边-非树边)）
直接跑（最小权的）KM即可
注意：
由于非树边和树边可能数量不同
而KM是最大权完美匹配，所以两边的点至少有一排应该是全部匹配上的，所以我们需要在树边（Y部）添加一些虚点
用来对应X部的点
这些虚点连出来的边都是0
在程序中有一个dfs树边的过程，这是方便在处理每个非树边的时候，可以一口气找到所有和非树边两端点连接的所有树边，便于计算边权
tip
好好读题
不能光会模板，概念原理证明都要通晓
板子要记扎实！！！
//这里写代码片
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int INF=0x33333333;
const int N=1000;
int n,m,cnt;
struct node{
int x,y,z;
};
node e[N];
struct node2{
int x,y,z,nxt,num;
};
node2 way[N];
int mp[55][55],st[N],tot=0,fa[N],cur[N],deep[N];
int Lx[N],Ly[N],slack[N],W[N][N],belong[N];
bool pp[N],L[N],R[N];
void add(int u,int w,int z,int k)
{
tot++;
way[tot].x=u;way[tot].y=w;way[tot].z=z;way[tot].num=k;way[tot].nxt=st[u];st[u]=tot;
tot++;
way[tot].x=w;way[tot].y=u;way[tot].z=z;way[tot].num=k;way[tot].nxt=st[w];st[w]=tot;
}
void dfs(int now,int f)
{
deep[now]=deep[f]+1;
for (int i=st[now];i;i=way[i].nxt)
if (way[i].y!=f)
{
fa[way[i].y]=now;
cur[way[i].y]=i; //和y相连的树边编号
dfs(way[i].y,now);
}
}
void build(int i) //i是非树边
{
int xx=e[i].x;
int yy=e[i].y;
while (xx!=yy)
{
if (deep[xx]>deep[yy])
{
int t=cur[xx]; //cur记录和xx相连的树边
W[cnt][way[t].num]=way[t].z-e[i].z; //num是边的编号,cut是当前非树边在X部中的编号
xx=fa[xx];
}
else
{
int t=cur[yy];
W[cnt][way[t].num]=way[t].z-e[i].z;
yy=fa[yy];
}
}
W[cnt][n+cnt]=0;
}
int match(int i)
{
L[i]=1;
for (int j=1;j<=m;j++)
if (!R[j])
{
int v=Lx[i]+Ly[j]-W[i][j];
if (!v)
{
R[j]=1;
if (!belong[j]||match(belong[j]))
{
belong[j]=i;
return 1;
}
}
else slack[j]=min(slack[j],v);
}
return 0;
}
int KM()
{
memset(Ly,0,sizeof(Ly));
memset(belong,0,sizeof(belong));
for (int i=1;i<=n;i++)
{
Lx[i]=W[i][1];
for (int j=2;j<=m;j++)
Lx[i]=max(Lx[i],W[i][j]);
}
for (int i=1;i<=n;i++)
{
for (int j=1;j<=m;j++) slack[j]=INF;
while (1)
{
memset(L,0,sizeof(L));
memset(R,0,sizeof(R));
if (match(i)) break;
int a=INF;
for (int j=1;j<=m;j++)
if (!R[j]) a=min(a,slack[j]);
for (int j=1;j<=n;j++)
if (L[j]) Lx[j]-=a;
for (int j=1;j<=m;j++)
if (R[j]) Ly[j]+=a;
else slack[j]-=a;
}
}
int ans=0;
for (int i=1;i<=m;i++) ans+=W[belong[i]][i];
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++)
scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z),mp[e[i].x][e[i].y]=i;
for (int i=1;i<n;i++)
{
int u,w;
scanf("%d%d",&u,&w);
int t=mp[u][w]; //边的编号
pp[t]=1; //树边
add(e[t].x,e[t].y,e[t].z,i);
}
dfs(1,0);
cnt=0;
for (int i=1;i<=m;i++)
if (!pp[i]) //非树边
{
cnt++;build(i);
}
m=n+cnt; n=cnt;
printf("%d
",KM());
}