A1261. happiness(吴确)
试题来源
2011中国国家集训队命题答辩
问题描述
高一一班的座位表是个n*m的矩阵，经过一个学期的相处，每个同学和前后左右相邻的同学互相成为了好朋友。这学期要分文理科了，每个同学对于选择文科与理科有着自己的喜悦值，而一对好朋友如果能同时选文科或者理科，那么他们又将收获一些喜悦值。作为计算机竞赛教练的scp大老板，想知道如何分配可以使得全班的喜悦值总和最大。
输入格式
第一行两个正整数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列的同学同时选择理科获得的额外喜悦值。
接下来是六个矩阵
第一个矩阵为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列的同学同时选择理科获得的额外喜悦值。
输出格式
输出一个整数，表示喜悦值总和的最大值
样例输入
1 2
1 1
100 110
1
1000
1 1
100 110
1
1000
样例输出
1210
样例说明
两人都选理，则获得100+110+1000的喜悦值。
数据规模和约定
对于10%以内的数据，n,m<=4
对于30%以内的数据，n,m<=8
对于100%以内的数据，n,m<=100 数据保证答案在2^30以内
对于100%的数据，时间限制为0.5s。
对于30%以内的数据，n,m<=8
对于100%以内的数据，n,m<=100 数据保证答案在2^30以内
对于100%的数据，时间限制为0.5s。
源代码
- #include<cstdio>
- #include<cstring>
- #include<iostream>
- #define EF if(ch==EOF) return x;
- #define rep for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
- #define rep1 for(int i=1;i<n;i++)for(int j=1;j<=m;j++)
- #define rep2 for(int i=1;i<=n;i++)for(int j=1;j<m;j++)
- using namespace std;
- const int Z=105;
- const int N=Z*Z;
- const int M=N*30;
- struct edge{int v,next,cap;}e[M<<1];int tot=1,head[N];
- int n,m,cnt,res,ans,S,T,dis[N],q[N+M];
- int a[Z][Z],b[Z][Z],id[Z][Z];
- inline int read(){
- int x=0,f=1;char ch=getchar();
- while(ch<'0'||ch>'9'){if(ch=='-')f=-1;EF;ch=getchar();}
- while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
- return x*f;
- }
- void add(int x,int y,int z){
- e[++tot].v=y;e[tot].cap=z;e[tot].next=head[x];head[x]=tot;
- e[++tot].v=x;e[tot].cap=0;e[tot].next=head[y];head[y]=tot;
- }
- void Add(int x,int y,int z){
- e[++tot].v=y;e[tot].cap=z;e[tot].next=head[x];head[x]=tot;
- e[++tot].v=x;e[tot].cap=z;e[tot].next=head[y];head[y]=tot;
- }
- bool bfs(){
- memset(dis,-1,sizeof dis);
- int h=0,t=1;q[t]=S;dis[S]=0;
- while(h!=t){
- int x=q[++h];
- for(int i=head[x];i;i=e[i].next){
- if(e[i].cap&&dis[e[i].v]==-1){
- dis[e[i].v]=dis[x]+1;
- if(e[i].v==T) return 1;
- q[++t]=e[i].v;
- }
- }
- }
- return 0;
- }
- int dfs(int x,int f){
- if(x==T) return f;
- int used=0,t;
- for(int i=head[x];i;i=e[i].next){
- if(e[i].cap&&dis[e[i].v]==dis[x]+1){
- t=dfs(e[i].v,min(e[i].cap,f));
- e[i].cap-=t;e[i^1].cap+=t;
- used+=t;f-=t;
- if(!f) return used;
- }
- }
- if(!used) dis[x]=-1;
- return used;
- }
- void dinic(){
- res=0;
- while(bfs()) res+=dfs(S,2e9);
- }
- int main(){
- n=read();m=read();
- rep a[i][j]=read();
- rep b[i][j]=read();
- rep id[i][j]=++cnt;
- S=0;T=cnt+1;
- #define u id[i][j]
- #define v id[i+1][j]
- rep{
- add(S,u,b[i][j]<<1);
- add(u,T,a[i][j]<<1);
- ans+=a[i][j]+b[i][j];
- }
- rep1 a[i][j]=read();
- rep1 b[i][j]=read();
- rep1{
- add(S,u,b[i][j]);add(S,v,b[i][j]);
- add(u,T,a[i][j]);add(v,T,a[i][j]);
- Add(u,v,a[i][j]+b[i][j]);
- ans+=a[i][j]+b[i][j];
- }
- #undef v
- #define v id[i][j+1]
- rep2 a[i][j]=read();
- rep2 b[i][j]=read();
- rep2{
- add(S,u,b[i][j]);add(S,v,b[i][j]);
- add(u,T,a[i][j]);add(v,T,a[i][j]);
- Add(u,v,a[i][j]+b[i][j]);
- ans+=a[i][j]+b[i][j];
- }
- dinic();
- res>>=1;
- printf("%d",ans-res);
- return 0;
- }