BZOJ2039 employee人员雇佣 && BZOJ2127 happiness 最小割模型

发布于 2017-07-29  6.26k 次阅读


[toggle hide="yes" title="题目:BZOJ2039 employee人员雇佣" color=""]2039: [2009国家集训队]employ人员雇佣

Description

作为一个富有经营头脑的富翁,小L决定从本国最优秀的经理中雇佣一些来经营自己的公司。这些经理相互之间合作有一个贡献指数,(我们用Ei,j表示i经理对j经理的了解程度),即当经理i和经理j同时被雇佣时,经理i会对经理j做出贡献,使得所赚得的利润增加Ei,j。当然,雇佣每一个经理都需要花费一定的金钱Ai,对于一些经理可能他做出的贡献不值得他的花费,那么作为一个聪明的人,小L当然不会雇佣他。 然而,那些没有被雇佣的人会被竞争对手所雇佣,这个时候那些人会对你雇佣的经理的工作造成影响,使得所赚得的利润减少Ei,j(注意:这里的Ei,j与上面的Ei,j 是同一个)。 作为一个效率优先的人,小L想雇佣一些人使得净利润最大。你可以帮助小L解决这个问题吗?

Input

第一行有一个整数N<=1000表示经理的个数 第二行有N个整数Ai表示雇佣每个经理需要花费的金钱 接下来的N行中一行包含N个数,表示Ei,j,即经理i对经理j的了解程度。(输入满足Ei,j=Ej,i)

Output

第一行包含一个整数,即所求出的最大值。

Sample Input

3

3 5 100

0 6 1

6 0 2

1 2 0

Sample Output

1

【数据规模和约定】

20%的数据中N<=10

50%的数据中N<=100

100%的数据中 N<=1000, Ei,j<=maxlongint, Ai<=maxlongint[/toggle]
[toggle hide="yes" title="题目:BZOJ2127 happiness" color=""]

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的非负整数

[/toggle]

这俩题是最小割的经典模型,即获得一个点的价值后还可能获得其与其他点的“绑定价值”。对于这样的题,可以先考虑仅有一个“限制关系”,即仅有一个获利规则,然后在此基础上继续添加限制条件。利用最小割,可以将“获得利益”转化为“舍弃最小利益”,然后用总获利减去舍弃的,即为获得的最大利益。在构图时,可以先搞个简单的模型,再考虑舍弃掉边后可能出现的情况,结合其实际含义为边赋流量。同时,如果遇到获利关系不好转化的情况,可以拆点、加点(例如happiness,可以拆点将同选文理的获利转成新边,考虑新模型可能出现的割法)。

 

[toggle hide="yes" title="" color=""]

 

[/toggle]
[toggle hide="yes" title="" color=""]

 

[/toggle]


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974