bzoj 3118: Orz the MST（单纯形）

时间：2022-08-29 20:03:59

题目链接：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<temp) temp=temp3,x=k;
            }
            if(temp2<temp*c[i])
            {
                s=i,l=x,temp2=temp*c[i];
            }
        }
        if(s==-1) break;
        pivot(l,s);
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++) if(B[j]==i) break;
        if(j<=m) ans[i]=b[j];
        else ans[i]=0;
    }
}

void print()
{
    int i,j;
    printf("v: %.3lf\n",v);
    printf("c:\n");
    for(i=1;i<=n;i++) printf("%.3lf ",c[i]); puts("");
    printf("A:\n");
    for(i=1;i<=m;i++)
    {
        for(j=1;j<=n;j++) printf("%.3lf ",A[i][j]);
        puts("");
    }
    printf("b:\n");
    for(i=1;i<=m;i++) printf("%.3lf ",b[i]); puts("");
    printf("B:\n");
    for(i=1;i<=m;i++) printf("%d ",B[i]); puts("");

    printf("N:\n");
    for(i=1;i<=n;i++) printf("%d ",N[i]); puts("");

}

int init()
{
    int i,j;
    int k=1;
    for(i=1;i<=m;i++) if(b[i]<b[k]) k=i;
    if(sgn(b[k])>=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) c[i]=0;
        else c[i]=-1;
    }
    pivot(k,n);
    simplex();

    if(sgn(ans[n])!=0) return 0;

    static int belongB[COL];
    clr(belongB,0);
    for(i=1;i<=m;i++)
    {
        if(B[i]>n) continue;
        belongB[B[i]]=i;
    }
    map<int,int> 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<int> 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);
}

相关文章