bzoj 3118: Orz the MST （单纯形）

Description

Input

Output

Sample Input

Sample Output

HINT

【Hint】样例解释：最优方案为：(1, 4)边权加2，代价6；(3, 5)边权加3，代价3；(3, 6)边权加4，代价8；(4, 5)边权减2，代价4；总代价21。数据范围：1<=N<=300, 1<=M, Wi, Ai, Bi<=1000。

Source

Mato_No1提供

题解：单纯形

一道不错的单纯形，需要用心想一下。

首先对于树边只可能减少，非树边只可能增加。

我们把树建好，考虑增加一条非树边，在什么情况下可能会替代一条树边，成为新的最小生成树？当非树边的两个端点之间路径上的边有比当前非树边小的时候，可以替换。

所有我们要保证路径上的所有边最终权值小于等于这条非树边。

那么我们可以得到wi-xi<=wj+xj,移项的xi+xj>=wi-wj

然后就得到了多个类似的式子，在满足所有式子的基础上最小化sigma (xi*c[i])

因为我们得到的式子是大于等于，所以需要用到对偶定理来转化求解。

#include<iostream>  #include<cstdio>  #include<algorithm>  #include<cstring>  #include<cmath>  #define N 1003  #define M 4003  #define eps 1e-8  using namespace std;  const double inf=1e20;int n,m,point[N],tot,nxt[N],v[N],num[N],c1[N],deep[N],val[N],pos[N],fa[N],cnt;  double ans,v1,b[M],a[N][M],c[M];  struct data{      int u,v,w,a,b,opt;  }e[N],e1[N];  void PRiov(int l,int e)  {      b[l]/=a[l][e];      for (int i=1;i<=m;i++)       if (i!=e) a[l][i]/=a[l][e];      a[l][e]=1/a[l][e];      for (int i=1;i<=n;i++)       if (fabs(a[i][e])>eps&&i!=l) {          b[i]-=b[l]*a[i][e];          for (int j=1;j<=m;j++)           if (j!=e) a[i][j]-=a[i][e]*a[l][j];          a[i][e]=-a[i][e]*a[l][e];       }      v1+=c[e]*b[l];      for (int i=1;i<=m;i++)       if (i!=e) c[i]-=c[e]*a[l][i];      c[e]=-c[e]*a[l][e];  }  double simple()  {      int i,l,e;      double t;      while (true){          for (i=1;i<=m;i++)            if (c[i]>eps) break;          e=i;          if (e==m+1) return v1;          t=inf;          for (int i=1;i<=n;i++)            if (a[i][e]>eps&&t>b[i]/a[i][e])             t=b[i]/a[i][e],l=i;          if (t==inf) return inf;          priov(l,e);      }  }  void add(int x,int y,int z,int k)  {      tot++; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; c1[tot]=z; num[tot]=k;      tot++; nxt[tot]=point[y]; point[y]=tot; v[tot]=x; c1[tot]=z; num[tot]=k;      //cout<<x<<" "<<y<<" "<<z<<endl;  }  void dfs(int x,int f)  {      deep[x]=deep[f]+1;      for (int i=point[x];i;i=nxt[i]){          if (v[i]==f) continue;          val[v[i]]=c1[i]; pos[v[i]]=num[i];          fa[v[i]]=x;          dfs(v[i],x);      }  }  void solve(int x,int y,int i)  {      while (x!=y) {          if (deep[x]>deep[y]) {              if (val[x]>e[i].w) {                  ++cnt; a[i][cnt]=1; a[pos[x]][cnt]=1;                  //cout<<i<<" "<<pos[x]<<endl;                  c[cnt]=val[x]-e[i].w;              }              x=fa[x];          }          else {              if (val[y]>e[i].w) {                  ++cnt; a[i][cnt]=1; a[pos[y]][cnt]=1;                  //cout<<i<<" "<<pos[y]<<endl;                  c[cnt]=val[y]-e[i].w;              }              y=fa[y];          }      }  }  int main()  {      freopen("a.in","r",stdin);      freopen("my.out","w",stdout);    scanf("%d%d",&n,&m);      for (int i=1;i<=m;i++) {         scanf("%d%d%d%d%d%d",&e[i].u,&e[i].v,&e[i].w,&e[i].opt,&e[i].a,&e[i].b);         if (e[i].opt) add(e[i].u,e[i].v,e[i].w,i),b[i]=e[i].b;         else b[i]=e[i].a;      }      dfs(1,0);     cnt=0;      for (int i=1;i<=m;i++) {          if (e[i].opt) continue;          solve(e[i].u,e[i].v,i);      }      n=cnt; swap(n,m);      /*for (int i=1;i<=m;i++) cout<<b[i]<<" "; cout<<endl;	for (int i=1;i<=n;i++) cout<<c[i]<<" "; cout<<endl;	for (int i=1;i<=m;i++,cout<<endl)	  for (int j=1;j<=n;j++) cout<<a[i][j]<<" ";	cout<<endl; */    ans=simple();      printf("%.0lf/n",ans);  }