BZOJ3511:土地划分 网络流

思路:

直接套用二元关系最小割,对于这道题而言非常朴素,而且不用考虑某些变量为负数还需要构造二分图的情况,很容易就水过去了.

现在我们仅考虑二元关系:(我们将所有收益预先加到一起,那么现在仅是需要减去最小的损失)

考虑两个点\(x,y\)以及一条边\(E(x,y)\):

\(x\in{A},y\in{A},cost=C_1=E_B\)

\(x\in{A},y\in{B},cost=C_2=E_A+E_B+E_C\)

\(x\in{B},y\in{A},cost=C_3=E_A+E_B+E_C\)

\(x\in{A},y\in{B},cost=C_4=E_A\)

连边\((S,x,a),(S,y,b),(x,T,c),(y,T,d),(x,y,e),(y,x,f)\).

随后不难发现:

\(C_1=c+d,C_2=b+c+e,C_3=a+d+f,C_4=a+b\)

好辣!如果我们能够直接解出\(a,b,c,d,e,f\)不是就非常好了么.

注意到如果\(a,b,c,d\)是负数我们并不用在意,因为\(a,c\)中只能选择一个,\(b,d\)中也只能选择一个,所以我们可以将边权均增大一个值,最终再减去即可.

可是\(e,f\)并不可以这样草率处理.

当\(C_2+C_3-C_1-C_2>0\)时,\(e,f\)可以取大于0的数,而\(a,b,c,d\)随意选择,问题可以解决.

如果不是的话,我们就需要在一对二元关系中,将其中一个点的意义反向,当然这有一个条件,二元关系必须不能存在奇环.不过这都是后话了.

这道题我们显然不用构造二分图,直接列出式子见图就行了.为了避免实数网络流将边权扩大二倍.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;
 
static const int INF=0x3f3f3f3f;
 
struct MaxflowSolver{
    static const int V=10010;
    static const int E=600010;
    int head[V],next[E],end[E],flow[E],ind;
    int gap[V],stk[V],d[V],top,cur[V];
    inline void reset(){ind=top=0,memset(head,-1,sizeof head);}
    inline void addedge(int a,int b,int f){int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f;}
    inline void make(int a,int b,int f){addedge(a,b,f),addedge(b,a,0);}
    inline void bfs(int T){
        static int q[V];int fr=0,ta=0;
        memset(gap,0,sizeof gap),memset(d,-1,sizeof d),++gap[d[T]=0],q[ta++]=T;
        while(fr^ta){
            int i=q[fr++];for(int j=head[i];j!=-1;j=next[j])if(d[end[j]]==-1)++gap[d[end[j]]=d[i]+1],q[ta++]=end[j];
        }
    }
    inline int Maxflow(int S,int T,int cnt){
        int res=0,u=S,ins,Min,i;bfs(T),memcpy(cur,head,sizeof cur);
        while(d[S]<cnt){
            if(u==T){
                for(Min=INF,i=0;i<top;++i)if(flow[stk[i]]<Min)Min=flow[stk[i]],ins=i;
                for(res+=Min,i=0;i<top;++i)flow[stk[i]]-=Min,flow[stk[i]^1]+=Min;
                u=end[stk[top=ins]^1];
            }
            if(u!=T&&!gap[d[u]-1])break;
            bool find=0;
            for(int&j=cur[u];j!=-1;j=next[j])if(flow[j]&&d[u]==d[end[j]]+1){find=1,ins=j;break;}
            if(find)stk[top++]=cur[u]=ins,u=end[ins];
            else{
                Min=cnt;for(int j=head[u];j!=-1;j=next[j])if(flow[j]&&d[end[j]]<Min)Min=d[end[j]],cur[u]=j;
                if(!--gap[d[u]])break;++gap[d[u]=Min+1];
                if(u!=S)u=end[stk[--top]^1];
            }
        }return res;
    }
}Stg;
 
int in[10010],out[10010];
 
int main(){
    int n,m;scanf("%d%d",&n,&m);register int i,j;
     
    Stg.reset();
    int S=0,T=n+1;
    in[1]=out[n]=INF;
    int a,b,x,res=0;
    for(i=2;i<n;++i)scanf("%d",&x),res+=x<<1,in[i]+=x<<1;
    for(i=2;i<n;++i)scanf("%d",&x),res+=x<<1,out[i]+=x<<1;
     
    int Ea,Eb,Ec;
    while(m--){
        scanf("%d%d%d%d%d",&a,&b,&Ea,&Eb,&Ec),res+=2*Ea+2*Eb;
        in[a]+=Ea,in[b]+=Ea,out[a]+=Eb,out[b]+=Eb;
        Stg.make(a,b,Ea+Eb+2*Ec),Stg.make(b,a,Ea+Eb+2*Ec);
    }
     
    for(i=1;i<=n;++i){
        if(in[i])Stg.make(S,i,in[i]);
        if(out[i])Stg.make(i,T,out[i]);
    }
     
    printf("%d",(res-Stg.Maxflow(S,T,n+2))>>1);
     
    return 0;
}