bzoj 2127 happiness

Posted by

题目链接

https://www.lydsy.com/JudgeOnline/problem.php?id=2127

题解

由于题目要求最大值,只需要将所有输入的满意度的和减去最小割的值即为答案,注意下面题解中对于不同情况下割集的解释。

源点向每个同学连边,容量为该同学选文科的满意度,每个同学向汇点连边,容量为该同学选理科的满意度,割这两条边分别表示选文科和不选理科;

对于相邻的两个同学\(x,y\),设他们都选文科的额外满意度为\(w_1\),都选理科的额外满意度为\(w_2\),由源点分别向\(x,y\)连边,容量为\(\frac {w_1}2\),分别记为边\(a,b\),由\(x,y\)分别向汇点连边,容量为\(\frac {w_2}2\),分别记为边\(c,d\);

割\(a,b\)表示两个人都不选文科,割\(c,d\)表示两个人都不选理科;

那如果分别选文、理科呢?这时候两个额外满意度都不会获得;

于是由\(x\)向\(y\)、由\(y\)向\(x\)分别连边,容量为\(\frac {w_1+w_2}2\),分别记为边\(e,f\);

割\(a,e,d\)表示\(x\)选理科,\(y\)选文科,割\(b,f,c\)表示\(x\)选文科,\(y\)选理科。

注意合并重边,权值乘\(2\)避免精度问题。

代码

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注