对于树边显然只需要减少权值，对于非树边显然只需要增加权值

设i不为树边，j为树边

X[i]:i增加量

X[j]:j减少量

C[i]:修改1单位i的代价

对于每条非树边i(u,v)，在树上u到v路径上的所有边j都需要满足

$W_i+X_i\geq W_j-X_j$

即

$X_i+X_j\geq W_j-W_i$

最后我们要最小化$\sum C_iX_i$

将矩阵转置，得到对偶问题，用线性规划单纯形法求解

 

#include
     
      #define rep(i,l,n) for(int i=l;i<=n;i++)const int N=1001,M=4000,inf=~0U>>2;int n,m,a[N][M],nxt[M],s,t,c,nn;int g[N],Nxt[N],v[N],ed,pre[N],id[N][N],head,tail,q[N];inline void cal(int l,int e){  a[l][e]=-1;t=M-1;  rep(i,0,m)if(a[l][i])nxt[t]=i,t=i;nxt[t]=-1;  rep(i,0,n)if(i!=l&&(t=a[i][e])){    a[i][e]=0;    for(int j=nxt[M-1];~j;j=nxt[j])a[i][j]+=a[l][j]*t;  }}int work(){  for(;;){int min=inf,l=0,e=0;    rep(i,1,m)if(a[0][i]>0){e=i;break;}    if(!e)return a[0][0];    rep(i,1,n)if(a[i][e]<0&&a[i][0]