BZOJ 3511 土地划分

AC通道：http://www.lydsy.com/JudgeOnline/problem.php?id=3511

题目分析：

　　看上去和前面的人员雇佣以及小M种田都很像。

　　最小割模型来求最大值，一般都是考虑怎样构图使得满足一个组合能被表示出来，而且当满足一个组合的时候，能产生或失去所需的效益。[割掉的是不要的]

　　我们将s与1相连，连为INF，这样就不会被割，n向t连边，同理。

　　因为1和n会有边连接，所以我们才多建出了节点s,t。

　　然后对于每个点i，s向i连wa[i],i向t连wb[i]，这样就满足了第一条性质。

　　对于ea,eb,ec的弄法，我们就先从s向u和向v连ea/2，从u和v向t连eb/2，然后在uv之间连一条双向的ea/2+eb/2+ec的边。

　　这样连边就能满足第二条性质了，反正就是脑补一下各种割法，就发现它奥妙重重，十分正确。

　　然后可以缩一下边，把s->i的边集以及i->t的合并一下[优化一下常数]。

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=;

const int maxm=;

const int INF=0x3f3f3f3f;

struct Node{

    int data,next,low;

}node[maxm*+maxn*];

#define now node[point].data

#define www node[point].low

#define then node[point].next

int n,m,cnt;

int s,t,ans;

int wa[maxn],wb[maxn];

int stoi[maxn],itot[maxn];

int cur[maxn],head[maxn];

int dis[maxn],que[maxn];

void add(int u,int v,int w){

    node[cnt].data=v;node[cnt].next=head[u];node[cnt].low=w;head[u]=cnt++;

    node[cnt].data=u;node[cnt].next=head[v];node[cnt].low=;head[v]=cnt++;

}

void add2(int u,int v,int w){

    node[cnt].data=v;node[cnt].next=head[u];node[cnt].low=w;head[u]=cnt++;

    node[cnt].data=u;node[cnt].next=head[v];node[cnt].low=w;head[v]=cnt++;

}

bool BFS(){

    memset(dis,-,sizeof(dis));

    int H=,T=;que[]=s;dis[s]=;

    while(H<T){

        H++;

        for(int point=head[que[H]];point!=-;point=then)

            if(www && dis[now]<){

                dis[now]=dis[que[H]]+;

                que[++T]=now;

            }

    }

    return dis[t]>;

}

int dfs(int x,int low){

    if(x==t) return low;

    int Low;

    for(int &point=cur[x];point!=-;point=then)

        if(www && dis[now]==dis[x]+){

            Low=dfs(now,min(low,www));

            if(Low){

                www-=Low,node[point^].low+=Low;

                return Low;

            }

        }

    return ;

}

int main(){

#ifndef ONLINE_JUDGE

    freopen("3511.in","r",stdin);

    freopen("3511.out","w",stdout);

#endif

    int u,v,Ea,Eb,Ec;

    scanf("%d%d",&n,&m);

    t=n+;

    for(int i=s;i<=t;i++) head[i]=-;

    for(int i=;i<n;i++) scanf("%d",&wa[i]),stoi[i]+=(wa[i]<<);

    for(int i=;i<n;i++) scanf("%d",&wb[i]),itot[i]+=(wb[i]<<);

    for(int i=;i<=m;i++){

        scanf("%d%d%d%d%d",&u,&v,&Ea,&Eb,&Ec);

        add2(u,v,Ea+Eb+(Ec<<));

        stoi[u]+=Ea,stoi[v]+=Ea;

        itot[u]+=Eb,itot[v]+=Eb;

    }

    for(int i=;i<=n;i++)

        ans+=stoi[i]+itot[i];

    stoi[]=itot[n]=INF;

    for(int i=;i<=n;i++)

        add(s,i,stoi[i]),add(i,t,itot[i]);

    int flag;

    while(BFS()){

        memcpy(cur,head,sizeof(head));

        while(flag=dfs(s,INF))

            ans-=flag;

    }

    ans>>=;

    printf("%d",ans);

    return ;

}

巴特西

BZOJ 3511 土地划分

最新文章

热门文章