【BZOJ2127】happiness 网络流最小割

自习室网速感人,我数数有5道题没写博客了,今天借了LLG的热点,好不容易登上来了QAQ

MD我今天才有时间发

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列的同学同时选择理科获得的额外喜悦值。

对于100%以内的数据,n,m<=100 所有喜悦值均为小于等于5000的非负整数

Output

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

这种题目大概是套路了,凡是出现了2选1,都可以考虑用最小割模型来做,这道题也不例外。

通常的套路是首先将所有的收益总和求出来,然后在不可兼得的两种收益中选择一种选择一个割掉,用总收益减去最小割就是答案。

这道题的建图分为两个部分,第一部分,常规建图,S->x一条边,容量为选文科的收益,x->T一条边,容量为选理科的收益。

第二部分,对于每一对相邻的点,新建两个节点A、B,S->A,A->x,A->y连三条边,容量都是xy同选文的收益,x->B,y->B,B->T三条边,通选理的收益。

然后dinic就好了(QAQ好久没写dinic,板子都写WA了几发)

code:

 

不如来评论一发?