【bzoj2127】happiness

2015.03.23 18:04 Mon | 10次阅读 | 旧日oi | 固定链接 | 源码

Description

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

Input

第一行两个正整数n,m。接下来是六个矩阵第一个矩阵为n行m列 此矩阵的第i行第j列的数字表示座位在第i行第j列的同学选择文科获得的喜悦值。第二个矩阵为n行m列 此矩阵的第i行第j列的数字表示座位在第i行第j列的同学选择理科获得的喜悦值。第三个矩阵为n-1行m列 此矩阵的第i行第j列的数字表示座位在第i行第j列的同学与第i+1行第j列的同学同时选择文科获得的额外喜悦值。第四个矩阵为n-1行m列 此矩阵的第i行第j列的数字表示座位在第i行第j列的同学与第i+1行第j列的同学同时选择理科获得的额外喜悦值。第五个矩阵为n行m-1列 此矩阵的第i行第j列的数字表示座位在第i行第j列的同学与第i行第j+1列的同学同时选择文科获得的额外喜悦值。第六个矩阵为n行m-1列 此矩阵的第i行第j列的数字表示座位在第i行第j列的同学与第i行第j+1列的同学同时选择理科获得的额外喜悦值。

Output

输出一个整数,表示喜悦值总和的最大值

Sample Input

1 2
1 1
100 110
1
1000

Sample Output

1210
【样例说明】
两人都选理,则获得100+110+1000的喜悦值。
【数据规模】
对于100%以内的数据,n,m<=100 所有喜悦值均为小于等于5000的非负整数

题解

今天又见识到了一种网络流模型,考试的时候因为没写long long导致暴力的40分都没了,光荣的再次rank inf……
这种题的建图方法很多,我的写法不用新建节点,时间上可能会快一点,但思维复杂度稍高一点,还可以新建节点,很直观,但是可能慢一点
具体建法,简单说一说:
建立源汇,每个点和原点连一条流量为选则文科的权值*2+和四周人共同选择文科所获得的权值,和汇点连选则理科的权值*2+和四周人共同选择理科所获得的权值,用sum记录所有的权值和。每两个点之间连一条权值为都选文的权值+都选理的权值的边。自己脑补一下课=可以看出,每个割都是一种选择方案,于是题目转化为最小割,用sum-最小割也就是答案了

我的程序

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<bitset>
#include<stack>
#include<ctime>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define ull unsigned long long
#define mod 
#define inf 0x3f3f3f3f
#define ll long long
#define maxn 50010
#define pos(x,y) ((x-1)*m+y)
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
struct edge{
    int to;
    int next;
    int flow;
}e[maxn*40];
int h[maxn],tp;
int a[maxn],b[maxn],tmp[maxn],S,T;
void ae(int u,int v,int w)
{
    e[tp].to=v;
    e[tp].next=h[u];
    e[tp].flow=w;
    h[u]=tp++;
}
void add(int u,int v,int w)
{
    ae(u,v,w);
    ae(v,u,0);
}
int n,m,t,ans;
int dis[maxn];
int q[maxn],f,ta;
bool bfs()
{
    memset(dis,0,sizeof(dis));
    f=ta=0;q[ta++]=S;dis[S]=1;
    while(f<ta)
    {
        int u=q[f++];
        for(int v,i=h[u];i!=-1;i=e[i].next)
        if(e[i].flow&&!dis[v=e[i].to])
        {
            dis[v]=dis[u]+1;
            if(v==T) return 1;
            q[ta++]=v;
        }
    }
    return 0;
}
int dfs(int u,int limit)
{
    if(u==T) return limit;
    int tmp,cost=0;
    for(int v,i=h[u];i!=-1;i=e[i].next)
    if(e[i].flow&&dis[v=e[i].to]==dis[u]+1)
    {
        tmp=dfs(v,min(limit-cost,e[i].flow));
        if(tmp){
            e[i].flow-=tmp;
            e[i^1].flow+=tmp;
            cost+=tmp;
            if(cost==limit) break;
        }
        else dis[v]=-1;
    }
    return cost;
}
int dinic()
{
    int ret=0;
    while(bfs()) 
    ret+=dfs(S,inf);
    return ret;
}
int main()
{
    n=read();m=read();S=0;T=n*m+1;
    memset(h,-1,sizeof(h));
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++) 
    a[pos(i,j)]+=read()*2,ans+=a[pos(i,j)];
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++) 
    b[pos(i,j)]+=read()*2,ans+=b[pos(i,j)];
    ans/=2;
    for(int i=1;i<n;i++)
    for(int j=1;j<=m;j++) 
    {
        tmp[pos(i,j)]=read();
        a[pos(i,j)]+=tmp[pos(i,j)];
        a[pos(i+1,j)]+=tmp[pos(i,j)];
    }
    for(int i=1;i<n;i++)
    for(int j=1;j<=m;j++) 
    {
        t=read();ans+=tmp[pos(i,j)]+t;
        b[pos(i,j)]+=t;
        b[pos(i+1,j)]+=t;
        ae(pos(i,j),pos(i+1,j),tmp[pos(i,j)]+t);
        ae(pos(i+1,j),pos(i,j),tmp[pos(i,j)]+t);
    }
    for(int i=1;i<=n;i++)
    for(int j=1;j<m;j++) 
    {
        tmp[pos(i,j)]=read();
        a[pos(i,j)]+=tmp[pos(i,j)];
        a[pos(i,j+1)]+=tmp[pos(i,j)];
    }
    for(int i=1;i<=n;i++)
    for(int j=1;j<m;j++) 
    {
        t=read();ans+=tmp[pos(i,j)]+t;
        b[pos(i,j)]+=t;
        b[pos(i,j+1)]+=t;
        ae(pos(i,j),pos(i,j+1),tmp[pos(i,j)]+t);
        ae(pos(i,j+1),pos(i,j),tmp[pos(i,j)]+t);
    }
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    add(S,pos(i,j),a[pos(i,j)]),add(pos(i,j),T,b[pos(i,j)]);
    printf("%d\n",ans-dinic()/2);
}```