P4412 题解
简化题意：一张无向图，给定一棵生成树，求最小的修改边权的代价使得这棵生成树是最小生成树，代价定义为修改前后一条边的边权变化量的绝对值。
思路
首先，发现让这棵树成为最小生成树不好直接处理，但是判定是否为最小生成树却相对更容易。判定的思路也很简单，对于每一条非树边 $(x,y)$，树上 $x$ 到 $y$ 的路径上的任意一条边边权都不能超过这条非树边的边权。
显然，树上的边边权一定不会减小，非树边边权一定不会变大。于是对于一条非树边 $y$ 和在树上的一条边 $x$，有 $w_x+|\Delta x|\geqslant w_y-|\Delta y|$，即 $|\Delta x|+|\Delta y|\geqslant w_y-w_x$。那我们把每一条边当做一个点，点权就是原来的边权，发现原问题就是**最小顶标号**问题，直接求二分图最大权完美匹配可以了。
由于不会写KM算法，就写了费用流。
贴一下代码
1 const int N=55,M=1551;
2 int n,m;
3 int e[N][N];
4 struct node{
5 int x,y,z;
6 }edge[M];
7 bool mark[M];
8 int cnt,ver[M],nxt[M],h[N],w[N],fa[N],eid[N],dep[N],id[N];
9 namespace Graph{
10 int cnt=1,ver[M<<6],nxt[M<<6],w[M<<6],c[M<<6],h[M<<1],s,t;
11 inline void add_edge(int x,int y,int z,int cost){
12 // cout<<x<<" "<<y<<" "<<cost<<endl;
13 cnt++;ver[cnt]=y;nxt[cnt]=h[x];h[x]=cnt;w[cnt]=z;c[cnt]=cost;
14 cnt++;ver[cnt]=x;nxt[cnt]=h[y];h[y]=cnt;w[cnt]=0;c[cnt]=-cost;
15 }
16 int flow[M<<1],dis[M<<1],lst[M<<1],pre[M<<1];
17 bool vis[M<<1];
18 inline bool bfsmax(){
19 queue<int>q;
20 memset(dis,0xc0,sizeof(dis));
21 memset(flow,0x3f,sizeof(flow));
22 memset(vis,0,sizeof(vis));
23 q.push(s);vis[s]=1,dis[s]=0,pre[t]=-1;
24 while(q.size()){
25 int x=q.front();
26 q.pop();
27 vis[x]=0;
28 for(int i=h[x];i;i=nxt[i]){
29 int y=ver[i];
30 if(w[i]>0&&dis[y]<dis[x]+c[i]){
31 dis[y]=dis[x]+c[i];
32 pre[y]=x;lst[y]=i;
33 flow[y]=min(w[i],flow[x]);
34 if(!vis[y]){
35 vis[y]=1;
36 q.push(y);
37 }
38 }
39 }
40 }
41 return pre[t]!=-1;
42 }
43 inline int getmax(){
44 int maxc=0;
45 while(bfsmax()){
46 if(dis[t]<0)break;
47 maxc+=flow[t]*dis[t];
48 int cur=t;
49 while(cur!=s){
50 w[lst[cur]]-=flow[t];
51 w[lst[cur]^1]+=flow[t];
52 cur=pre[cur];
53 }
54 }
55 return maxc;
56 }
57 inline int solve(){
58 s=0,t=m+1;
59 for(int i=1;i<n;i++)add_edge(s,i,1,0);
60 for(int i=n;i<=m;i++)add_edge(i,t,1,0);
61 return getmax();
62 }
63 }
64 inline void add_edge(int x,int y,int z){cnt++;ver[cnt]=y;nxt[cnt]=h[x];h[x]=cnt;w[cnt]=z;}
65 inline void dfs(int x){
66 dep[x]=dep[fa[x]]+1;
67 for(int i=h[x];i;i=nxt[i]){
68 int y=ver[i];
69 if(y!=fa[x]){
70 fa[y]=x;
71 eid[y]=w[i];
72 dfs(y);
73 }
74 }
75 }
76 inline void modify(int x,int y,int z){
77 if(dep[x]<dep[y])swap(x,y);
78 while(dep[x]>dep[y]){
79 Graph::add_edge(id[eid[x]],id[z],1,edge[eid[x]].z-edge[z].z);
80 x=fa[x];
81 }
82 while(x^y){
83 Graph::add_edge(id[eid[x]],id[z],1,edge[eid[x]].z-edge[z].z);
84 Graph::add_edge(id[eid[y]],id[z],1,edge[eid[y]].z-edge[z].z);
85 x=fa[x],y=fa[y];
86 }
87 }
88 int main(){
89 ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
90 cin>>n>>m;
91 for(int i=1;i<=m;i++){
92 int x,y,z;
93 cin>>x>>y>>z;
94 e[x][y]=e[y][x]=i;
95 edge[i]=(node){x,y,z};
96 }
97 for(int i=1;i<n;i++){
98 int x,y;
99 cin>>x>>y;
100 mark[e[x][y]]=1;
101 add_edge(x,y,e[x][y]);add_edge(y,x,e[x][y]);
102 }
103 for(int i=1,t1=0,t2=n-1;i<=m;i++){
104 if(mark[i])id[i]=++t1;
105 else id[i]=++t2;
106 }
107 dfs(1);
108 for(int i=1;i<=m;i++){
109 if(!mark[i]){
110 int x=edge[i].x,y=edge[i].y;
111 modify(x,y,i);
112 }
113 }
114 cout<<Graph::solve()<<endl;
115 return 0;
116 }
标签：int,题解,边权,add,edge,eid,P4412,id From： https://www.cnblogs.com/Xttttr/p/17629845.html