题目链接：http://www.lydsy.com:808/JudgeOnline/problem.php?id=3118

题意：给出一个图以及图中指定的n-1条边组成的生成树。每条边权值加1或者减去1都有相应的代价。求一个最小代价使得给出的边是最小生成树。

思路：对于每条非树边，必与某些树边形成环。设该非树边的权值为w2,某树边的权值为 w1。最后非树边增加x2,树边减少x1，那么w1-x1<=w2+x2。这样我们可以得到一些式子。代价也知道，这样就转化成线性规划问题。题目求的是最小值，我们可以将目标方程的系数取反求最大值。

单纯形的步骤：

（1）求出一个初始解；

（2）迭代。

 

（1）这个题的系数矩阵A是全么模：1、元素都是0，-1，1；2、任意子方阵的行列式为0，-1,1。

（2）据说A是全么模时解是整数解，因此此题可直接用单纯形。

 

const int COL=1005;const int ROW=30005;int n,m,B[ROW],N[COL];double A[ROW][COL],b[ROW],c[COL],v;double ans[COL];int sgn(double x){    if(x>1e-8) return 1;    if(x<-1e-8) return -1;    return 0;}//B中第l个替换N中第e个void pivot(int l,int e){    int i,j;    double temp=A[l][e];    b[l]/=temp; A[l][e]=1/temp;    for(i=1;i<=n;i++) if(i!=e) A[l][i]/=temp;    for(i=1;i<=m;i++) if(i!=l)    {        b[i]-=A[i][e]*b[l];        for(j=1;j<=n;j++) if(j!=e) A[i][j]-=A[i][e]*A[l][j];        A[i][e]=-A[i][e]/temp;    }    v+=b[l]*c[e];    for(i=1;i<=n;i++) if(i!=e) c[i]-=c[e]*A[l][i];    c[e]*=-A[l][e];    swap(B[l],N[e]);}void simplex(){    int i,j,k,x;    int l,s;    double temp,temp1,temp2,temp3;    while(1)    {        temp2=-dinf; s=-1;        for(i=1;i<=n;i++) if(sgn(c[i])>0)        {            temp=dinf;            for(k=1;k<=m;k++) if(sgn(A[k][i])>0)            {                temp3=b[k]/A[k][i];                if(temp3
     
      =0)    {        for(i=1;i<=n;i++) N[i]=i;        for(i=1;i<=m;i++) B[i]=n+i;        v=0;        simplex();        return 1;    }    static double tmpC[COL];    for(i=1;i<=n;i++) tmpC[i]=c[i];    tmpC[n+1]=0;    n++;    for(i=1;i<=m;i++) A[i][n]=-1;    for(i=1;i<=n;i++) N[i]=i;    for(i=1;i<=m;i++) B[i]=n+i;    v=0;    for(i=1;i<=n;i++)    {        if(i
      
       n) continue;        belongB[B[i]]=i;    }    map
       
         mp;    for(i=1;i<=n;i++) mp[N[i]]=i;    clr(c,0);    v=0;    for(i=1;i<=n;i++)    {        if(!belongB[i])        {            c[mp[i]]+=tmpC[i];        }        else        {            v+=tmpC[i]*b[belongB[i]];            int j;            for(j=1;j<=n;j++)            {                c[j]+=tmpC[i]*(-A[belongB[i]][j]);            }        }    }    c[mp[n]]=0;    for(i=1;i<=m;i++) A[i][mp[n]]=0;    simplex();    n--;    return 1;}struct node{    int u,v,id,w,next;};node edges[ROW];int e;int head[COL];void add(int u,int v,int w,int id){    e++;    edges[e].u=u;    edges[e].v=v;    edges[e].w=w;    edges[e].id=id;    edges[e].next=head[u];    head[u]=e;}int h[COL],up[COL],down[COL];int eNum;int inq[COL],KK;int pre[COL];void build(int s,int t,int p){    int i;    for(i=pre[t];i!=-1;)    {        int w1=edges[i].w;        int w2=edges[p*2].w;        m++;        A[m][edges[i].id]=-1;        A[m][p]=-1;        b[m]=w2-w1;        int u=edges[i].u;        i=pre[u];    }}void bfs(int s,int t,int p){    queue
        
          Q;    Q.push(s);    KK++;    inq[s]=KK;    pre[s]=-1;    while(!Q.empty())    {        int u=Q.front();        Q.pop();        int i;        for(i=head[u];i!=-1;i=edges[i].next)        {            int v=edges[i].v;            int id=edges[i].id;            if(!h[id]||KK==inq[v]) continue;            pre[v]=i;            if(v==t)            {                build(s,t,p);                return;            }            Q.push(v);            inq[v]=KK;        }    }}int main(){    n=myInt();    eNum=myInt();    clr(head,-1);    int i;    for(i=1;i<=eNum;i++)    {        int u,v,w;        scanf("%d%d%d%d%d%d",&u,&v,&w,&h[i],&up[i],&down[i]);        add(u,v,w,i);        add(v,u,w,i);    }    for(i=1;i<=eNum;i++) if(!h[i])    {        int t=i*2;        bfs(edges[t].u,edges[t].v,i);    }    for(i=1;i<=eNum;i++) c[i]=h[i]?-down[i]:-up[i];    n=eNum;    if(!init())    {        puts("no solution");    }    double res=-v;    if(res<1e-10) res=0;    printf("%.0lf\n",-v);}