2127: happiness
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
1 1
100 110
1
1000
Sample Output
1210
【样例说明】
两人都选理，则获得100+110+1000的喜悦值。
【数据规模】
对于100%以内的数据，n,m<=100 所有喜悦值均为小于等于5000的非负整数
【样例说明】
两人都选理，则获得100+110+1000的喜悦值。
【数据规模】
对于100%以内的数据，n,m<=100 所有喜悦值均为小于等于5000的非负整数
最小割
正常版，详情参见黄学长博客。。。
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
#define MaxP 23333
#define MaxT 233333
const int INF=0x3f3f3f3f;
int N,M,Ans,tot,S,T;
int first[MaxP],next[MaxT],end[MaxT],cap[MaxT],cur[MaxP],lev[MaxP];
int a[MaxP],b[MaxP];
queue <int> Q;
void Add(int x,int y,int z){
next[++tot]=first[x]; first[x]=tot; end[tot]=y; cap[tot]=z;
next[++tot]=first[y]; first[y]=tot; end[tot]=x; cap[tot]=0;
}
int Number(int x,int y){
return (x-1)*M+y;
}
void Init(){
tot=1;
scanf("%d%d",&N,&M);
S=0; T=N*M+1;
for (int i=1;i<=N;++i)
for (int j=1;j<=M;++j){
int u=Number(i,j);
scanf("%d",&a[u]);
a[u]*=2;
Ans+=a[u];
}
for (int i=1;i<=N;++i)
for (int j=1;j<=M;++j){
int u=Number(i,j);
scanf("%d",&b[u]);
b[u]*=2;
Ans+=b[u];
}
for (int i=1;i<N;++i)
for (int j=1;j<=M;++j){
int x,u1=Number(i,j),u2=Number(i+1,j);
scanf("%d",&x);
a[u1]+=x; a[u2]+=x; Ans+=2*x;
Add(u1,u2,x); Add(u2,u1,x);
}
for (int i=1;i<N;++i)
for (int j=1;j<=M;++j){
int x,u1=Number(i,j),u2=Number(i+1,j);
scanf("%d",&x);
b[u1]+=x; b[u2]+=x; Ans+=2*x;
Add(u1,u2,x); Add(u2,u1,x);
}
for (int i=1;i<=N;++i)
for (int j=1;j<M;++j){
int x,u1=Number(i,j),u2=Number(i,j+1);
scanf("%d",&x);
a[u1]+=x; a[u2]+=x; Ans+=2*x;
Add(u1,u2,x); Add(u2,u1,x);
}
for (int i=1;i<=N;++i)
for (int j=1;j<M;++j){
int x,u1=Number(i,j),u2=Number(i,j+1);
scanf("%d",&x);
b[u1]+=x; b[u2]+=x; Ans+=2*x;
Add(u1,u2,x); Add(u2,u1,x);
}
int cnt=N*M;
for (int i=1;i<=cnt;++i)
Add(S,i,a[i]),Add(i,T,b[i]);
}
bool BFS(){
for (;!Q.empty();) Q.pop();
memset(lev+1,-1,sizeof(int)*T);
lev[S]=0;
cur[S]=first[S];
Q.push(S);
for (;!Q.empty();){
int u=Q.front();
Q.pop();
for (int k=first[u],v;v=end[k],k;k=next[k])
if (cap[k]&&lev[v]<0){
lev[v]=lev[u]+1;
cur[v]=first[v];
if (v==T) return true;
Q.push(v);
}
}
return false;
}
int Dinic(int u,int flow){
if (u==T) return flow;
int ans=0;
for (int &k=cur[u],v;v=end[k],k;k=next[k])
if (cap[k]&&lev[v]>lev[u]){
int tmp=Dinic(v,min(cap[k],flow-ans));
if (tmp){
cap[k]-=tmp;
cap[k^1]+=tmp;
ans+=tmp;
if (ans==flow) return flow;
}
}
if (ans!=flow) lev[u]=-1;
return ans;
}
int main(){
Init();
for (;BFS();)
Ans-=Dinic(S,INF);
printf("%d\n",Ans/2);
}
其实蒟蒻wy表示看到这道题一开始想到的是文理分科的方法。。。
于是后来又写了个逗比版。。。
除了跑得巨慢外并没有什么问题。。。
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
#define MaxN 101
#define MaxP 66666
#define MaxT 666666
const int INF=0x3f3f3f3f;
int N,M,Ans,tot,S,T,cnt,Num[MaxN][MaxN];
int first[MaxP],next[MaxT],end[MaxT],cap[MaxT],cur[MaxP],lev[MaxP];
queue <int> Q;
void Add(int x,int y,int z){
next[++tot]=first[x]; first[x]=tot; end[tot]=y; cap[tot]=z;
next[++tot]=first[y]; first[y]=tot; end[tot]=x; cap[tot]=0;
}
int Get(){
char Ch;
while ((Ch=getchar())<'0'||Ch>'9');
int Num=Ch-'0';
while ((Ch=getchar())>='0'&&Ch<='9')
Num=Num*10+Ch-'0';
return Num;
}
void Init(){
tot=1;
N=Get(); M=Get();
for (int i=1;i<=N;++i)
for (int j=1;j<=M;++j)
Num[i][j]=++cnt;
S=0; T=cnt*5+1;
for (int i=1;i<=N;++i)
for (int j=1;j<=M;++j){
int u=Num[i][j],x=Get();
Ans+=x;
Add(S,u,x);
}
for (int i=1;i<=N;++i)
for (int j=1;j<=M;++j){
int u=Num[i][j],x=Get();
Ans+=x;
Add(u,T,x);
}
for (int i=1;i<N;++i)
for (int j=1;j<=M;++j){
int u1=Num[i][j],u2=Num[i+1][j],x=Get();
int o=u1+cnt;
Add(S,o,x);
Ans+=x;
Add(o,u1,x); Add(o,u2,x);
}
for (int i=1;i<N;++i)
for (int j=1;j<=M;++j){
int u1=Num[i][j],u2=Num[i+1][j],x=Get();
int o=u1+2*cnt;
Add(o,T,x);
Ans+=x;
Add(u1,o,x); Add(u2,o,x);
}
for (int i=1;i<=N;++i)
for (int j=1;j<M;++j){
int u1=Num[i][j],u2=Num[i][j+1],x=Get();
int o=u1+3*cnt;
Add(S,o,x);
Ans+=x;
Add(o,u1,x); Add(o,u2,x);
}
for (int i=1;i<=N;++i)
for (int j=1;j<M;++j){
int u1=Num[i][j],u2=Num[i][j+1],x=Get();
int o=u1+4*cnt;
Add(o,T,x);
Ans+=x;
Add(u1,o,x); Add(u2,o,x);
}
}
bool BFS(){
for (;!Q.empty();) Q.pop();
memset(lev+1,-1,sizeof(int)*T);
lev[S]=0;
cur[S]=first[S];
Q.push(S);
for (;!Q.empty();){
int u=Q.front();
Q.pop();
for (int k=first[u],v;v=end[k],k;k=next[k])
if (cap[k]&&lev[v]<0){
lev[v]=lev[u]+1;
cur[v]=first[v];
if (v==T) return true;
Q.push(v);
}
}
return false;
}
int Dinic(int u,int flow){
if (u==T) return flow;
int ans=0;
for (int &k=cur[u],v;v=end[k],k;k=next[k])
if (cap[k]&&lev[v]>lev[u]){
int tmp=Dinic(v,min(cap[k],flow-ans));
if (tmp){
cap[k]-=tmp;
cap[k^1]+=tmp;
ans+=tmp;
if (ans==flow) return flow;
}
}
if (ans!=flow) lev[u]=-1;
return ans;
}
int main(){
Init();
for (;BFS();)
Ans-=Dinic(S,INF);
printf("%d\n",Ans);
}
评论 (0)
