也是神了。感觉一天都在好神的题里面游荡。
本来是想复习一下KM的，结果一眼过去？？？
结果做法是这样的，把树边和非树边分成两个集合
根据贪心的思想，要搞的话肯定树边减少，而非树边增加。
对于在原树中的一条边的两点x，y，如果在最小生成树里面x到y的那一条路径的边有比这条边大的，那我们肯定得做点什么。
抽象就是这样wi+di>=wj-dj wi是原树的边权，wj最小生成树路径上的边权，d是我们人为的改变。
变形一下 ---> di+dj>=wj-wi 其中wj和wi已知。 。。。。顶标？？（原谅我以前没有理性的理解这个算法）被秀飞
感觉有点差分约束的味道？？然后构图我也觉得很难。。。
先把最小生成树遍历一次，然后再枚举非树边两个点往上跳
感觉我跑的挺慢的。
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; int n; struct sc { int x,y,d; }e[21000];int mp[1100][1100]; bool istree[21000]; struct node { int x,y,d,id,next; }a[21000];int len,last[21000]; void ins(int x,int y,int d,int id) { len++; a[len].x=x;a[len].y=y;a[len].d=d;a[len].id=id; a[len].next=last[x];last[x]=len; } int fa[1100],dep[1100],pre[11000]; void dfs(int x,int fr) { for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(y!=fr) { fa[y]=x; dep[y]=dep[x]+1; pre[y]=k; dfs(y,x); } } } int love[1100][1100]; void build(int now,int i) { int x=e[i].x,y=e[i].y; while(x!=y) { if(dep[x]>dep[y])swap(x,y); int k=pre[y]; love[now][a[k].id]=a[k].d-e[i].d; y=fa[y]; } } int exg[1100],exb[1100]; bool vg[1100],vb[1100]; int match[1100],need[1100]; bool findboy(int x) { vg[x]=true; for(int i=1;i<=n;i++) { if(vb[i]==false) { int gap=exg[x]+exb[i]-love[x][i]; if(gap==0) { vb[i]=true; if(match[i]==0||findboy(match[i])==true) { match[i]=x; return true; } } else need[i]=min(need[i],gap); } } return false; } void KM() { memset(match,0,sizeof(match)); memset(exg,0,sizeof(exg)); memset(exb,0,sizeof(exb)); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) exg[i]=max(exg[i],love[i][j]); for(int i=1;i<=n;i++) { memset(need,63,sizeof(need)); while(1) { memset(vg,false,sizeof(vg)); memset(vb,false,sizeof(vb)); if(findboy(i)==true)break; int d=2147483647; for(int j=1;j<=n;j++) if(vb[j]==false)d=min(d,need[j]); for(int j=1;j<=n;j++) { if(vg[j]==true)exg[j]-=d; if(vb[j]==true)exb[j]+=d; else need[j]-=d; } } } int ans=0; for(int i=1;i<=n;i++) ans+=love[match[i]][i]; printf("%d ",ans); } int main() { freopen("mst.in","r",stdin); freopen("mst.out","w",stdout); int m,x,y,d; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].d); mp[e[i].x][e[i].y]=i; } memset(istree,false,sizeof(istree)); for(int i=1;i<n;i++) { scanf("%d%d",&x,&y); int id=mp[x][y]; istree[id]=true; ins(x,y,e[id].d,i);ins(y,x,e[id].d,i); } dep[1]=1;dfs(1,0); memset(love,0,sizeof(love)); for(int i=1,tp=0;i<=m;i++) if(istree[i]==false)build(++tp,i); n=max(n-1,m-(n-1)); KM(); return 0; }