【COGS 1873】 [国家集训队2011]happiness(吴确) 最小割

这是一种最小割模型，就是对称三角，中间双向边，我们必须满足其最小割就是满足题目条件的互斥关系的最小舍弃，在这道题里面我们S表示文T表示理，中间一排点是每个人，每个人向两边连其选文或者选理的价值，中间每两个点之间连他们的高兴度，然后我们就要分析，并作出改变，对于任意两个点我们要么割一个z要么两边某一边全割掉，那么我们割两边时不经舍弃了其选理（文）的价值还舍弃了他们一起的价值，对于z我们不仅要割掉了一文一理，而且还把所有的一起全部舍弃因此，于是理（文）边还要带一半的一起，中间的边为双向都为两个（半一起）。

#include <cstdio>

#include <cstring>

#include <iostream>

#define N 2005

#define r register

using namespace std;

inline int read()

{

    r int sum=;

    r char ch=getchar();

    while(ch<''||ch>'')ch=getchar();

    while(ch>=''&&ch<='')

    {

        sum=(sum<<)+(sum<<)+ch-'';

        ch=getchar();

    }

    return sum;

}

struct VIA

{

    int to,next,f;

}c[N*N*];

int head[N*N],t=;

int like[N][N][];

int n,m,S,T;

int together1[N][N],together2[N][N];

int Hash[N][N];

inline void add(int x,int y,int z)

{

    c[++t].to=y;

    c[t].f=z;

    c[t].next=head[x];

    head[x]=t;

}

int q[N*N],top,tail,deep[N*N];

inline bool bfs()

{

    memset(deep,,sizeof(deep));

    q[]=S;

    deep[S]=;

    top=tail=;

    while(top<=tail)

    {

      r int x=q[top++];

      if(x==T)return ;

      for(int i=head[x];i;i=c[i].next)

      if(c[i].f&&deep[c[i].to]==)

      {

        deep[c[i].to]=deep[x]+;

        q[++tail]=c[i].to;

      }

    }

    return ;

}

inline int Min(int x,int y)

{

     return x<y?x:y;

}

int dfs(int x,int v)

{

     if(x==T||!v)return v;

     r int ret=;

     for(int i=head[x];i;i=c[i].next)

     if(c[i].f&&deep[c[i].to]==deep[x]+)

     {

       r int f=Min(c[i].f,v);

       r int w=dfs(c[i].to,f);

       v-=w;

       ret+=w;

       c[i].f-=w;

       c[i^].f+=w;

       if(!v)break;

     }

     if(!ret)deep[x]=-;

     return ret;

}

inline int dinic()

{

    r int ans=;

    while(bfs())ans+=dfs(S,0x7f7f7f7f);

    return ans;

}

int main()

{

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

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

    r int ans=;

    n=read(),m=read();

    S=n*m+;

    T=S+;

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

      for(r int j=;j<=m;++j)

        like[i][j][]=*read(),ans+=like[i][j][];

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

      for(r int j=;j<=m;++j)

        like[i][j][]=*read(),ans+=like[i][j][];

    for(r int i=,x;i<n;++i)

      for(r int j=;j<=m;++j)

        x=read(),together1[i][j]=x,like[i][j][]+=x,like[i+][j][]+=x,ans+=x*;

    for(r int i=,x;i<n;++i)

      for(r int j=;j<=m;++j)

        x=read(),together1[i][j]+=x,like[i][j][]+=x,like[i+][j][]+=x,ans+=x*;

    for(r int i=,x;i<=n;++i)

      for(r int j=;j<m;++j)

        x=read(),together2[i][j]=x,like[i][j][]+=x,like[i][j+][]+=x,ans+=x*;

    for(r int i=,x;i<=n;++i)

      for(r int j=;j<m;++j)

        x=read(),together2[i][j]+=x,like[i][j][]+=x,like[i][j+][]+=x,ans+=x*;

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

      for(r int j=;j<=m;++j)

        Hash[i][j]=(i-)*m+j,add(S,Hash[i][j],like[i][j][]),add(Hash[i][j],S,),add(Hash[i][j],T,like[i][j][]),add(T,Hash[i][j],);

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

      for(r int j=;j<=m;++j)

        add(Hash[i][j],Hash[i+][j],together1[i][j]),add(Hash[i+][j],Hash[i][j],together1[i][j]);

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

      for(r int j=;j<m;++j)

        add(Hash[i][j],Hash[i][j+],together2[i][j]),add(Hash[i][j+],Hash[i][j],together2[i][j]);

    ans-=dinic();

    ans/=;

    printf("%d",ans);

}

巴特西

【COGS 1873】 [国家集训队2011]happiness(吴确) 最小割

最新文章

热门文章