BZOJ3118: Orz the MST

题解:

首先树上的边权只可能减少.非树边上的权值只可能增大.

然后就有对于一条非树边,修改后的权值要不小于所有它覆盖的树边被修改后的权值.

注意题目中其实是保证树边数目$\times$非树边数目$\leq{4000}$的.

然后对偶一下发现有初始可行解,直接上单纯形.

代码:

#include<cstdio>
#include<cctype>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define inf 0x3f3f3f3f
struct Linear_Programming{
    static const int N=4010;
    static const int M=1010;
    int n,m,A[M][N],b[M],c[N],v,B[M],nB[N];
    int _c[N],_v,_nB[N],Bins[N+M],nBins[N+M];
    inline void pivot(int l,int e){
        int i,j;
        for(i=1;i<=n;++i)
            if(i!=e)
                A[l][i]/=A[l][e];
        b[l]/=A[l][e];
        A[l][e]=1/A[l][e];
        for(i=1;i<=m;++i)
            if(i!=l&&A[i][e]!=0){
                for(j=1;j<=n;++j)
                    if(j!=e)
                        A[i][j]-=A[i][e]*A[l][j];
                b[i]-=A[i][e]*b[l];
                A[i][e]*=-A[l][e];
            }
        for(i=1;i<=n;++i)
            if(i!=e)
                c[i]-=c[e]*A[l][i];
        v+=c[e]*b[l];
        c[e]*=-A[l][e];
        swap(B[l],nB[e]);
    }
    inline int Simplex(){
        int i,j,l,e,lim;
        while(1){
            for(e=0,i=1;i<=n;++i)
                if(c[i]>0){
                    e=i;
                    break;
                }
            if(!e)
                return v;
            for(lim=inf,i=1;i<=m;++i)
                if(A[i][e]>0&&lim>b[i]/A[i][e]){
                    l=i;
                    lim=b[i]/A[i][e];
                }
            if(lim==inf)
                return inf;
            pivot(l,e);
        }
    }
    inline bool init(){
        int i,j,l,e,min_b=inf;
        for(i=1;i<=m;++i)
            if(b[i]<min_b){
                min_b=b[i];
                l=i;
            }
        if(min_b>=0)
            return 1;
        memcpy(_c,c,sizeof c);
        _v=v;
        memcpy(_nB,nB,sizeof nB);
        memset(c,0,sizeof c);
        v=0;
        nB[++n]=0;
        c[n]=-1;
        for(i=1;i<=m;++i)
            A[i][n]=-1;
        pivot(l,n);
        if(Simplex()<0)
            return 0;
        else{
            for(i=1;i<=m;++i)
                if(B[i]==0){
                    for(j=1;j<=n;++j)
                        if(A[i][j]!=0){
                            pivot(i,j);
                            break;
                        }
                }
            for(i=1;i<=n;++i)
                if(nB[i]==0)
                    e=i;
            --n;
            for(i=e;i<=n;++i)
                nB[i]=nB[i+1];
            for(i=1;i<=m;++i)
                for(j=e;j<=n;++j)
                    A[i][j]=A[i][j+1];
            memset(c,0,sizeof c);
            v=_v;
            for(i=1;i<=n;++i)
                nBins[nB[i]]=i;
            for(i=1;i<=m;++i)
                Bins[B[i]]=i;
            for(i=1;i<=n;++i)
                if(nBins[_nB[i]])
                    c[nBins[_nB[i]]]+=_c[i];
                else{
                    v+=_c[i]*b[Bins[_nB[i]]];
                    for(j=1;j<=n;++j)
                        c[j]-=_c[i]*A[Bins[_nB[i]]][j];
                }
            return 1;
        }
    }
}g;
 
#define N 310
#define M 1010
int head[N],next[M<<1],end[M<<1],F[M<<1],ind=2;
inline void addedge(int a,int b,int f){
    int q=ind++;
    end[q]=b;
    next[q]=head[a];
    head[a]=q;
    F[q]=f;
}
inline void make(int a,int b,int f){
    addedge(a,b,f);
    addedge(b,a,f);
}
 
struct Edge{
    int a,b,c,f,A,B;
    inline void read(){
        scanf("%d%d%d%d%d%d",&a,&b,&c,&f,&A,&B);
    }
}E[M];
 
int pa[N],pa_edge[N];
inline void dfs(int x,int fa){
    for(int j=head[x];j;j=next[j])
        if(end[j]!=fa&&F[j]){
            pa[end[j]]=x;
            pa_edge[end[j]]=j>>1;
            dfs(end[j],x);
        }
}
 
int main(){
#ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
#endif
 
    int n,m;
    scanf("%d%d",&n,&m);
    int i,j;
    for(i=1;i<=m;++i)
        E[i].read();
    for(i=1;i<=m;++i)
        make(E[i].a,E[i].b,E[i].f);
    int lim=0;
    for(i=1;i<=m;++i)
        if(!E[i].f){
            pa[E[i].a]=0;
            dfs(E[i].a,-1);
            for(j=E[i].b;j!=E[i].a;j=pa[j]){
                ++lim;
                g.A[pa_edge[j]][lim]=1;
                g.A[i][lim]=1;
                g.c[lim]=E[pa_edge[j]].c-E[i].c;
            }
        }
    for(i=1;i<=m;++i)
        g.b[i]=E[i].f?E[i].B:E[i].A;
    g.n=lim;
    g.m=m;
    for(i=1;i<=g.n;++i)
        g.nB[i]=i;
    for(i=1;i<=g.m;++i)
        g.B[i]=g.n+i;
    g.init();
    cout<<g.Simplex()<<endl;
    return 0;
}