[BZOJ2127/Luogu1646]happiness(网络流)

发布于 2018-02-03  51 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ2127/Luogu1646]happiness(网络流)

Description

高一一班的座位表是个n*m的矩阵,经过一个学期的相处,每个同学和前后左右相邻的同学互相成为了好朋友。这学期要分文理科了,每个同学对于选择文科与理科有着自己的喜悦值,而一对好朋友如果能同时选文科或者理科,那么他们又将收获一些喜悦值。作为计算机竞赛教练的scp大老板,想知道如何分配可以使得全班的喜悦值总和最大。

Http

BZOJ
Luogu

Tag

网络流

解决思路

这一题类似的,先把求最大收益转化为求最小损失,即先把所有的收益都加起来,然后求一个最小的损失即最小割。
一个人选文还是选理分别与源汇点连边,假设源点\(S\)表示选文,汇点\(T\)表示选理,这个比较好处理,但是,与旁边的人的选择就不好处理了,因为这里两人同时选文和同时选理的收益是不一样的。
怎么办呢?总共只有\(4\)种可能,所以我们把这四种情况列出来。
设\(x->y\)表示\(x\)到\(y\)这条边上的容量,设\(u\)表示两人同时选文的收益,\(v\)为两人同时选理的收益,则有:
若两人同时选文,则割掉的边是\(x->T,y->T\),损失是\(v\)。
若两人同时选理,则割掉的边是\(S->x,S->y\),损失是\(u\)
若\(x\)文\(y\)理,则割掉的边是\(x->T,S->y,x->y\),损失是\(u+v\)
若\(x\)理\(y\)文,则割掉的边是\(S->x,y->T,y->x\)
综上,四个方程就是
\((x->T)+(y->T)=v \\ (S->x)+(S->y)=u \\ (x->T)+(S->y)+(x->y)=u+v \\ (S->x)+(y->T)+(y->x)=u+v\)
但是这个方程是无法直接解的。考虑到实际上不管是哪一组解都是可以的,不妨设\((x->T)==(y->T)==\frac{v}{2}\),同理有\((S->x)==(S->y)==\frac{u}{2}\),那么就有\((x->y)==(y->x)==\frac{u+v}{2}\)
由于除以二会导致可能出现小数,所以考虑把所有的容量先乘以二变成整数,最后求出最小割再除以二即可。

代码

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

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxMap=101;
const int maxN=maxMap*maxMap;
const int maxM=maxN*100;
const int inf=2147483647;

class Edge
{
public:
    int v,flow;
};

int n,m,S,T;
int Mat1[maxMap][maxMap],Mat2[maxMap][maxMap],Mat3[maxMap][maxMap],Mat4[maxMap][maxMap],Mat5[maxMap][maxMap],Mat6[maxMap][maxMap],Id[maxMap][maxMap];
int edgecnt=-1,Head[maxN],Next[maxM];
Edge E[maxM];
int Depth[maxN],Queue[maxN],cur[maxN];

void Add_Edge(int u,int v,int flow,int opt);
bool Bfs();
int dfs(int u,int flow);

int main()
{
    mem(Head,-1);
    scanf("%d%d",&n,&m);
    int Ans=0;
    for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) scanf("%d",&Mat1[i][j]),Ans+=Mat1[i][j];
    for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) scanf("%d",&Mat2[i][j]),Ans+=Mat2[i][j];
    for (int i=1;i<n;i++) for (int j=1;j<=m;j++) scanf("%d",&Mat3[i][j]),Ans+=Mat3[i][j];
    for (int i=1;i<n;i++) for (int j=1;j<=m;j++) scanf("%d",&Mat4[i][j]),Ans+=Mat4[i][j];
    for (int i=1;i<=n;i++) for (int j=1;j<m;j++) scanf("%d",&Mat5[i][j]),Ans+=Mat5[i][j];
    for (int i=1;i<=n;i++) for (int j=1;j<m;j++) scanf("%d",&Mat6[i][j]),Ans+=Mat6[i][j];
    int idcnt=0;
    for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) Id[i][j]=++idcnt;
    S=idcnt+1;T=idcnt+2;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
        {
            Add_Edge(S,Id[i][j],Mat1[i][j]*2+Mat3[i][j]+Mat3[i-1][j]+Mat5[i][j]+Mat5[i][j-1],0);
            Add_Edge(Id[i][j],T,Mat2[i][j]*2+Mat4[i][j]+Mat4[i-1][j]+Mat6[i][j]+Mat6[i][j-1],0);
            if (i!=n) Add_Edge(Id[i][j],Id[i+1][j],Mat3[i][j]+Mat4[i][j],1);
            if (j!=m) Add_Edge(Id[i][j],Id[i][j+1],Mat5[i][j]+Mat6[i][j],1);
        }
    int mxflow=0;
    while (Bfs())
    {
        for (int i=1;i<=T;i++) cur[i]=Head[i];
        while (int di=dfs(S,inf)) mxflow+=di;
    }
    printf("%d\n",Ans-mxflow/2);
    return 0;
}

void Add_Edge(int u,int v,int flow,int opt)
{
    edgecnt++;Next[edgecnt]=Head[u];Head[u]=edgecnt;E[edgecnt].v=v;E[edgecnt].flow=flow;
    edgecnt++;Next[edgecnt]=Head[v];Head[v]=edgecnt;E[edgecnt].v=u;E[edgecnt].flow=opt*flow;
    return;
}

bool Bfs()
{
    mem(Depth,-1);
    int h=1,t=0;Queue[1]=S;Depth[S]=1;
    do
    {
        int u=Queue[++t];
        for (int i=Head[u];i!=-1;i=Next[i])
            if ((E[i].flow>0)&&(Depth[E[i].v]==-1))
                Depth[Queue[++h]=E[i].v]=Depth[u]+1;
    }
    while (t!=h);
    if (Depth[T]==-1) return 0;
    return 1;
}

int dfs(int u,int flow)
{
    if (u==T) return flow;
    for(int &i=cur[u];i!=-1;i=Next[i])
        if ((Depth[E[i].v]==Depth[u]+1)&&(E[i].flow>0))
        {
            int di=dfs(E[i].v,min(flow,E[i].flow));
            if (di)
            {
                E[i].flow-=di;
                E[i^1].flow+=di;
                return di;
            }
        }
    return 0;
}

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ2127/Luogu1646]happiness(网络流)


HNCJ OIer 一枚