Description

Input

Output

Sample Input

Sample Output

HINT

【Hint】樣例解釋：最優(yōu)方案為：(1, 4)邊權(quán)加2，代價(jià)6；(3, 5)邊權(quán)加3，代價(jià)3；(3, 6)邊權(quán)加4，代價(jià)8；(4, 5)邊權(quán)減2，代價(jià)4；總代價(jià)21。數(shù)據(jù)范圍：1<=N<=300, 1<=M, Wi, Ai, Bi<=1000。

Source

Mato_No1提供

題解：?jiǎn)渭冃?/p>

一道不錯(cuò)的單純形，需要用心想一下。

首先對(duì)于樹邊只可能減少，非樹邊只可能增加。

我們把樹建好，考慮增加一條非樹邊，在什么情況下可能會(huì)替代一條樹邊，成為新的最小生成樹？當(dāng)非樹邊的兩個(gè)端點(diǎn)之間路徑上的邊有比當(dāng)前非樹邊小的時(shí)候，可以替換。

所有我們要保證路徑上的所有邊最終權(quán)值小于等于這條非樹邊。

那么我們可以得到wi-xi<=wj+xj,移項(xiàng)的xi+xj>=wi-wj

然后就得到了多個(gè)類似的式子，在滿足所有式子的基礎(chǔ)上最小化sigma (xi*c[i])

因?yàn)槲覀兊玫降氖阶邮谴笥诘扔冢孕枰玫綄?duì)偶定理來轉(zhuǎn)化求解。

#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);  }