题面
分析
根据贪心的思想我们得到几条性质：
1.生成树上的边权减小，非树边的边权增加
2.每条边最多被修改一次
设改变量的绝对值为d
对于一条非树边(j:(u,v))，树上u->v的路径上的任意一条边i的边权(w_ileq j)，否则把i替换成j可以得到一棵更小的生成树
因此有(w_i-d_i leq w_j+d_j)
转换一下有(w_i-w_j leq d_i+d_j)
发现形式和KM算法中的顶标很相似，所以把原图中的边看成点，变化值为顶标，新图的边权(w_i-w_j)
跑KM算法即可
实现中需要注意几个细节：
由于两边的点数不一定=n,所以要加虚点，把两边的点补成n,左部虚点i和右部1~n连边，边权为0 ，右部同理
代码中只要把邻接矩阵的初始值全部设为0即可,这样相当于该虚点和任意点都可以匹配，且权值为0
匹配其他的点时如果发现不满足，就把虚点的匹配点换一下 ,KM算法结束后这个点随便匹配另一个点即可，因为权值为0，不影响答案
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<utility>
#define maxn 55
#define maxm 805
#define maxlog 32
#define INF 0x3f3f3f3f
using namespace std;
int n,m;
int is_tree[maxm];
map<pair<int,int>,int>edge_id;
struct edge {
int from;
int to;
int len;
int next;
} G[maxm<<1],T[maxm<<1];
int sz=1;
int head[maxn];
void add_edge1(int u,int v) {
sz++;
T[sz].from=u;
T[sz].to=v;
T[sz].next=head[u];
head[u]=sz;
}
int log2n;
int deep[maxn];
int anc[maxn][maxlog];
void dfs1(int x,int fa) {
deep[x]=deep[fa]+1;
anc[x][0]=fa;
for(int i=1; i<=log2n; i++) {
anc[x][i]=anc[anc[x][i-1]][i-1];
}
for(int i=head[x]; i; i=T[i].next) {
int y=T[i].to;
if(y!=fa) {
dfs1(y,x);
}
}
}
int lca(int x,int y) {
if(deep[x]<deep[y]) swap(x,y);
for(int i=log2n; i>=0; i--) {
if(deep[anc[x][i]]>=deep[y]) x=anc[x][i];
}
if(x==y) return x;
for(int i=log2n; i>=0; i--) {
if(anc[x][i]!=anc[y][i]) {
x=anc[x][i];
y=anc[y][i];
}
}
return anc[x][0];
}
int dist[maxm][maxm];
void add_edge2(int u,int v,int w){
w=max(w,0);
// printf("debug:%d %d
",u,v);
dist[u][v]=w;
}
void make_graph(int x,int y,int ed){
int l=lca(x,y);
if(x==l){
for(int i=y;i!=l;i=anc[i][0]){
int t=edge_id[make_pair(i,anc[i][0])];
add_edge2(t,ed,G[t].len-G[ed].len);
}
}else if(y==l){
for(int i=x;i!=l;i=anc[i][0]){
int t=edge_id[make_pair(i,anc[i][0])];
add_edge2(t,ed,G[t].len-G[ed].len);
}
}else{
for(int i=x;i!=l;i=anc[i][0]){
int t=edge_id[make_pair(i,anc[i][0])];
add_edge2(t,ed,G[t].len-G[ed].len);
}
for(int i=y;i!=l;i=anc[i][0]){
int t=edge_id[make_pair(i,anc[i][0])];
add_edge2(t,ed,G[t].len-G[ed].len);
}
}
}
int la[maxm];
int lb[maxm];
int match[maxm];
int va[maxm];
int vb[maxm];
int delta;
int dfs2(int x){
va[x]=1;
for(int y=1;y<=m;y++){
if(!vb[y]){
if(la[x]+lb[y]==dist[x][y]){
vb[y]=1;
if(!match[y]||dfs2(match[y])){
match[y]=x;
return 1;
}
}
}
}
return 0;
}
int KM(){
for(int i=1;i<=m;i++){
la[i]=-INF;
for(int j=1;j<=m;j++){
la[i]=max(la[i],dist[i][j]);
}
lb[i]=0;
}
for(int i=1;i<=m;i++){
while(1){
memset(va,0,sizeof(va));
memset(vb,0,sizeof(vb));
delta=INF;
if(dfs2(i)) break;
for(int j=1;j<=m;j++){
if(!va[j]) continue;
for(int k=1;k<=m;k++){
if(!vb[k]){
delta=min(delta,la[j]+lb[k]-dist[j][k]);
}
}
}
for(int j=1;j<=m;j++){
if(va[j]) la[j]-=delta;
if(vb[j]) lb[j]+=delta;
}
}
}
int ans=0;
for(int i=1;i<=m;i++){
ans+=dist[match[i]][i];
}
return ans;
}
int main() {
scanf("%d %d",&n,&m);
log2n=log2(n)+1;
int u,v,w;
for(int i=1;i<=m;i++){
scanf("%d %d %d",&u,&v,&w);
G[i].from=u;
G[i].to=v;
G[i].len=w;
edge_id[make_pair(u,v)]=edge_id[make_pair(v,u)]=i;
}
int p;
for(int i=1;i<n;i++){
scanf("%d %d",&u,&v);
p=edge_id[make_pair(u,v)];
add_edge1(u,v);
add_edge1(v,u);
is_tree[p]=1;
}
dfs1(1,0);
// memset(dist,0x3f,sizeof(dist));
for(int i=1;i<=m;i++){
if(!is_tree[i]) make_graph(G[i].from,G[i].to,i);
}
// for(int i=1;i<=m;i++){
// for(int j=1;j<=m;j++){
// if(dist[i][j]==INF) printf("INF ",dist[i][j]);
// else printf("%d ",dist[i][j]);
// }
// printf("
");
// }
printf("%d
",KM());
}