给出一个带权的连通无向图，对于其中的每条边i，在原来边权的基础上，其边权每增加1需要付出的代价为Ai，边权每减少1需要付出的代价为Bi，现在指定该图的一棵生成树，求通过修改边权，使得该生成树成为图的一棵最小生成树，需要付出的最少总代价。 1<=N<=300, 1<=M, Wi, Ai, Bi<=1000
有个显然的结论就是我们只会减小指定树边的权值，只会增加非树边的权值。 然后我们考虑满足什么的时候指定的树是最小生成树，其实就是对于每条非树边，它的两端点在树中对路径上的边都比这条非树边短。 然后直接上单纯形即可。对偶之后可以简化一下，不用求初始解了。
#include<cstdio> #include<cmath> #include<algorithm> using namespace std; const double eps=1e-8; const int maxn=505, maxe=4005, maxk=10005; int n,m,K,id[maxk*2]; double a[1005][maxk]; int son[maxn],nxt[maxe],fir[maxn],tot=1; struct Edge{ int x,y,w,c; Edge(int t1=0,int t2=0,int t3=0,int t4=0){ x=t1;y=t2;w=t3;c=t4; } } Es[maxe]; void add(int x,int y){ son[++tot]=y; nxt[tot]=fir[x]; fir[x]=tot; } void Pivot(int l,int e){ swap(id[n+l],id[e]); double t=a[l][e]; a[l][e]=1; for(int i=0;i<=n;i++) a[l][i]/=t; for(int i=0;i<=m;i++) if(i!=l&&fabs(a[i][e])>eps){ t=a[i][e]; a[i][e]=0; for(int j=0;j<=n;j++) a[i][j]-=t*a[l][j]; } } bool Simplex(){ while(1){ int l=0,e=0; double _min=1e+50; for(int i=1;i<=n;i++) if(a[0][i]>eps){ e=i; break; } if(!e) break; for(int i=1;i<=m;i++) if(-a[i][e]<-eps&&a[i][0]/a[i][e]<_min) _min=a[i][0]/a[i][e], l=i; if(!l) return false; Pivot(l,e); } return true; } bool dfs(int x,int pre,int t,int now){ if(x==t) return true; for(int j=fir[x];j;j=nxt[j]) if(son[j]!=pre){ if(dfs(son[j],x,t,now)){ int d=min(j,j^1)/2; //printf("%d--%d + %d--%d ...\n",Es[now].x,Es[now].y,Es[d].x,Es[d].y); K++; a[0][K]=Es[d].w-Es[now].w; a[now][K]=a[d][K]=1; return true; } } return false; } int main(){ freopen("bzoj3118.in","r",stdin); freopen("bzoj3118.out","w",stdout); scanf("%d%d",&n,&m); int len1=0,len2=0; for(int i=1;i<=m;i++){ int t1,t2,t3,t4,t5,t6; scanf("%d%d%d%d%d%d",&t1,&t2,&t3,&t4,&t5,&t6); if(t4){ Es[++len1]=Edge(t1,t2,t3,t6); add(t1,t2); add(t2,t1); } else Es[n-1+(++len2)]=Edge(t1,t2,t3,t5); } for(int i=n;i<=m;i++) dfs(Es[i].x,Es[i].x,Es[i].y,i); for(int i=1;i<=m;i++) a[i][0]=Es[i].c; n=K; m=m; for(int i=1;i<=n;i++) id[i]=i; Simplex(); printf("%d\n",(int)(-a[0][0]+0.5)); return 0; }