首页 > 代码库 > BZOJ 2127: happiness

BZOJ 2127: happiness

2024-09-20 12:49:18   208人阅读

2127: happiness

Time Limit: 51 Sec  Memory Limit: 259 MB
Submit: 2084  Solved: 1028

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的非负整数
 
首先我们来吐槽一下
技术分享

什么狗屁BZOJ，钱收的越来越多，事却办不利索，TLE了一晚上，一次比一次慢，最后一次是STD；

 

#include<iostream>#include<cstring>#include<cstdio>#include<queue>#include<algorithm>using namespace std;const int S=0;#define T (m*n+1)#define maxm 10100#define INF 30000000struct Edge{ int to,value,next; }e[1001001];int tot=1,head[maxm],ans,n,m;int a[110][110],b[110][110];void Add_Edge(int u,int v,int w){    e[++tot].to=v;e[tot].value=http://www.mamicode.com/w;    e[tot].next=head[u];head[u]=tot;}queue<int> q;int pre(int x,int y){ return ((x*n)-n+y); }namespace Max_Flow{    int dep[maxm];    bool BFS(){        memset(dep,-1,sizeof dep );        while(!q.empty()) q.pop();        dep[S]=0;q.push(S);        while(!q.empty()){            int u=q.front();q.pop();            for(int i=head[u];i;i=e[i].next){                int v=e[i].to;                if(dep[v]==-1&&e[i].value){                    dep[v]=dep[u]+1; q.push(v);                    if(v==T) return true;                }            }        }        return false;    }    int Dinic(int u,int flow){        if(u==T) return flow;        int ret=flow;        for(int i=head[u];i;i=e[i].next){            int v=e[i].to;            if(dep[v]==dep[u]+1&&e[i].value){                int x=Dinic(v,min(e[i].value,ret));                ret-=x;e[i].value-=x;e[i^1].value+=x;            }        }        if(ret) dep[u]=-1;        return flow-ret;    }}int main(){    scanf("%d%d",&m,&n);    for(int i=1;i<=m;i++)        for(int j=1;j<=n;j++){            scanf("%d",&a[i][j]);            ans+=a[i][j]; a[i][j] <<= 1;        }    for(int i=1;i<=m;i++)        for(int j=1;j<=n;j++){            scanf("%d",&b[i][j]);            ans+=b[i][j]; b[i][j] <<= 1;        }    for(int i=1;i<m;i++)        for(int x,j=1;j<=n;j++){            scanf("%d",&x);ans+=x;            a[i][j]+=x; a[i+1][j]+=x;            int u=pre(i,j),v=pre(i+1,j);            Add_Edge(u,v,x);Add_Edge(v,u,x);        }    for(int i=1;i<m;i++)        for(int x,j=1;j<=n;j++){            scanf("%d",&x);ans+=x;            b[i][j]+=x; b[i+1][j]+=x;            int u=pre(i,j),v=pre(i+1,j);            Add_Edge(u,v,x);Add_Edge(v,u,x);        }    for(int i=1;i<=m;i++)        for(int x,j=1;j<n;j++){            scanf("%d",&x);ans+=x;            a[i][j]+=x; a[i][j+1]+=x;            int u=pre(i,j),v=pre(i,j+1);            Add_Edge(u,v,x);Add_Edge(v,u,x);        }    for(int i=1;i<=m;i++)        for(int x,j=1;j<n;j++){            scanf("%d",&x);ans+=x;            b[i][j]+=x; b[i][j+1]+=x;            int u=pre(i,j),v=pre(i,j+1);            Add_Edge(u,v,x);Add_Edge(v,u,x);        }    for(int i=1;i<=m;i++)        for(int j=1;j<=n;j++){            int P=pre(i,j);            Add_Edge(S,P,a[i][j]);            Add_Edge(P,S,a[i][j]);            Add_Edge(P,T,b[i][j]);            Add_Edge(T,P,b[i][j]);        }    using namespace Max_Flow;    ans <<= 1;    while(BFS()) ans-=Dinic(S,INF);    printf("%d\n",(ans>>1));    return 0;}

 

BZOJ 2127: happiness


联系
我们