2127: happiness
Time Limit: 51 Sec Memory Limit: 259 MBSubmit: 2335 Solved: 1130
[Submit][Status][Discuss]
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的非负整数
?题解：此题与上一题相似，不过这次是选择不同时不能得到额外的权值，无需翻转源汇，S对所有点来说都是文科，T对所有点来说都是理科。
对于单独两个点来说，只有两种情况。
?若两个人都选文科，需要割掉第2，4条边，代价为两个人选理科分别的贡献，以及他们一起选理科的贡献，因为所有的点都是等价的，2，4边的权值除各自选理科贡献外再加上一半的额外贡献。
若两个人都选择理科同理。
?若两个人选择不同，假设x选择文科，y选择理科，那么需要割掉2，3，5。
此时2，3权值和为分别选择科目的贡献和一半的同时选择理科和同时选择文
科的贡献。还需再减去剩余的一半，即应是5的权值。(x，y间要建双向边。)
#include<iostream>
#include<cmath>#include<cstring>
#include<cstdio>
#include<queue>
#include<map>
#include<cstdlib>
#include<algorithm>
#define V 105
#define mod 1000000007
#define LL long long
using namespace std;
int n,m,T,S;
int f,nn,ss;
int a[V][V],g[V][V],pre[V*V],dep[V*V],q[V*V];
double sd[V][V],sb[V][V];
int s[8][V][V];
struct da
{
int to,next;
double dis;//,cast;
}Edge[V*V*V];
int head[V*V],tot;
inline void add(int x,int y,double zz)
{
Edge[tot].to=y;
Edge[tot].dis=zz;
// Edge[tot].cast=st;
Edge[tot].next=head[x];
head[x]=tot++;
Edge[tot].to=x;
Edge[tot].dis=0;
//Edge[tot].cast=-st;
Edge[tot].next=head[y];
head[y]=tot++;
}
bool Bfs() { // bfs建立层次图
memset(dep, 0, sizeof(dep));
int hd,tl;
hd = tl = 0;
q[++ tl] = S, dep[S] = 1;
while(hd<tl) {
int op = q[++hd];
for(int i = head[op] ; i != -1 ; i = Edge[i].next) {
if(Edge[i].dis&&(!dep[Edge[i].to])) {
dep[Edge[i].to] = dep[op]+1;
q[++ tl] = Edge[i].to;
if(Edge[i].to==T) return true;
}
}
}
return false;
}
double Dfs(int op,double fw) {
if(op==T) return fw;
double tmp=fw,k;
for(int i = head[op] ; i != -1 ; i = Edge[i].next) {
if(Edge[i].dis&&tmp&&dep[Edge[i].to]==dep[op]+1) {
k = Dfs(Edge[i].to, min(Edge[i].dis, tmp));
if(!k) {
dep[Edge[i].to] = 0;
continue;
}
Edge[i].dis-= k, Edge[i^1].dis+= k,tmp-= k;
}
}
return fw-tmp;
}
double solve()
{
double flow=0;
while(Bfs())
{
flow+=Dfs(S,mod);
}
return flow;
}
inline int haha()
{
// freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);
//freopen("flyer.in","r",stdin); freopen("flyer.out","w",stdout);
memset(head,-1,sizeof(head));
cin>>n>>m;
int uu=0,pd=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
scanf("%d",&s[1][i][j]);
pd+=s[1][i][j];
g[i][j]=++uu;
}
T=g[n][m]+1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
scanf("%d",&s[2][i][j]);
pd+=s[2][i][j];
}
for(int i=1;i<=n-1;i++)
for(int j=1;j<=m;j++)
{
scanf("%d",&s[3][i][j]);
pd+=s[3][i][j];
sd[i][j]+=s[3][i][j];
sd[i+1][j]+=s[3][i][j];
}
for(int i=1;i<=n-1;i++)
for(int j=1;j<=m;j++)
{
scanf("%d",&s[4][i][j]);
pd+=s[4][i][j];
sb[i][j]+=s[4][i][j];
sb[i+1][j]+=s[4][i][j];
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m-1;j++)
{
scanf("%d",&s[5][i][j]);
pd+=s[5][i][j];
sd[i][j]+=s[5][i][j];
sd[i][j+1]+=s[5][i][j];
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m-1;j++)
{
scanf("%d",&s[6][i][j]);
pd+=s[6][i][j];
sb[i][j]+=s[6][i][j];
sb[i][j+1]+=s[6][i][j];
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
sd[i][j]/=2;
sb[i][j]/=2;
add(0,g[i][j],sd[i][j]+s[1][i][j]);
add(g[i][j],T,sb[i][j]+s[2][i][j]);
//printf("%d &&%d %lf\n",i,j,double(sd[i][j]+s[1][i][j]));
//printf("%d %d %lf\n",i,j,double(sb[i][j]+s[2][i][j]));
//if(i>1)
//add(g[i][j],g[i-1][j],double(s[3][i][j]+s[4][i][j])/2);
if(i<n)
{
add(g[i][j],g[i+1][j],double(s[3][i][j]+s[4][i][j])/2);
add(g[i+1][j],g[i][j],double(s[3][i][j]+s[4][i][j])/2);
//printf("%d &^%d %lf\n",i,j,double(s[3][i][j]+s[4][i][j])/2);
}
if(j<m)
{
add(g[i][j],g[i][j+1],double(s[5][i][j]+s[6][i][j])/2);
add(g[i][j+1],g[i][j],double(s[5][i][j]+s[6][i][j])/2);
// printf("%d ** %d %lf\n",i,j,double(s[5][i][j]+s[6][i][j])/2);
}
}
printf("%d",int(pd-solve()));
return 0;
}
int gg=haha();
int main()
{;}