BruceJay's Blog

BZOJ3511 土地划分

| Comments

To start with

又是一道最小割。

Problem

Solution

还是按习惯的思路做这道题。
S集表示划分给A,T集表示划分给B。所以S向x连容量va[x]的边,x向T连容量vb[x]的边。
考虑每一条边(x,y),如果两个都划分给A,花费为vb[x]+vb[y]+eb;都划分给B,花费为va[x]+va[y]+ea;x划分给A,y划分给B,花费为ea+eb+ec+va[y]+vb[x]。所以S向x,y分别连容量ea/2的边,x,y分别向T连容量eb/2的边,x,y之间互连容量ea/2+eb/2+ec的边。
由于出现了除以2,所以所有容量应同时乘以2。

Code

#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 10100;
const int M = 150100;
const int INF = 0x3f3f3f3f;
struct Edge{int u,v,cap,flow,nxt;}e[M];
int cur[N]; int head[N]; int h[N];
int va[N]; int vb[N];
queue<int> q;
int n,m,t,ans=0,cnt=1;

inline int read()
{
    int t=1,x=0; char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') t=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return t*x;
}

void Addedge(int u,int v,int c)
{
    e[++cnt]=(Edge){u,v,c,0,head[u]}; head[u]=cnt;
    e[++cnt]=(Edge){v,u,0,0,head[v]}; head[v]=cnt;
}

void Addedge2(int u,int v,int c)
{
    e[++cnt]=(Edge){u,v,c,0,head[u]}; head[u]=cnt;
    e[++cnt]=(Edge){v,u,c,0,head[v]}; head[v]=cnt;
}

bool Bfs()
{
    memset(h,-1,sizeof(h));
    h[0]=0; q.push(0);
    while(!q.empty()){
        int u=q.front(); q.pop();
        for(int i=head[u];i;i=e[i].nxt)
            if(h[e[i].v]==-1 && e[i].cap>e[i].flow){
                h[e[i].v]=h[u]+1; q.push(e[i].v);
            }
    }
    return h[t]!=-1;
}

int Dfs(int u,int now)
{
    int flow=0;
    if(u==t || !now) return now;
    for(int& i=cur[u];i;i=e[i].nxt)
        if(h[e[i].v]==h[u]+1){
            int f=Dfs(e[i].v,min(now,e[i].cap-e[i].flow));
            e[i].flow+=f; e[i^1].flow-=f;
            flow+=f; now-=f; if(!now) break;
        }
    return flow;
}

void Dinic()
{
    while(Bfs()){
        memcpy(cur,head,sizeof(cur));
        ans-=Dfs(0,INF);
    }
}

int main()
{
    int u,v,ea,eb,ec;
    freopen("3511.in","r",stdin);
    freopen("3511.out","w",stdout);
    n=read(); m=read(); t=n+1;
    va[1]=INF; vb[n]=INF;
    for(int i=2;i<n;i++) va[i]=read()<<1,ans+=va[i];
    for(int i=2;i<n;i++) vb[i]=read()<<1,ans+=vb[i];
    for(int i=1;i<=m;i++){
        u=read(); v=read();
        ea=read(); eb=read(); ec=read();
        ans+=(ea+eb)<<1;
        va[u]+=ea; vb[u]+=eb;
        va[v]+=ea; vb[v]+=eb;
        Addedge2(u,v,ea+eb+(ec<<1));
    }
    for(int i=1;i<=n;i++) Addedge(0,i,va[i]);
    for(int i=1;i<=n;i++) Addedge(i,t,vb[i]);
    Dinic();
    printf("%d",ans>>1);
    return 0;
}

Last but not least

Bruce只会刷裸题。

Comments

comments powered by Disqus