BZOJ3438 - Click Here
Description
小M在MC里开辟了两块巨大的耕地A和B（你可以认为容量是无穷），现在，小P有n中作物的种子，每种作物的种子有1个（就是可以种一棵作物）（用1…n编号），现在，第i种作物种植在A中种植可以获得ai的收益，在B中种植可以获得bi的收益，而且，现在还有这么一种神奇的现象，就是某些作物共同种在一块耕地中可以获得额外的收益，小M找到了规则中共有m种作物组合，第i个组合中的作物共同种在A中可以获得c1i的额外收益，共同总在B中可以获得c2i的额外收益，所以，小M很快的算出了种植的最大收益，但是他想要考考你，你能回答他这个问题么？
Input
第一行包括一个整数n
第二行包括n个整数，表示ai第三行包括n个整数，表示bi第四行包括一个整数m接下来m行，
对于接下来的第i行：第一个整数ki，表示第i个作物组合中共有ki种作物，
接下来两个整数c1i，c2i，接下来ki个整数，表示该组合中的作物编号。输出格式
Output
只有一行，包括一个整数，表示最大收益
Solutions
显然文理分科模型，考虑最小割解决。
对于每种作物$i$，连边$S \stackrel{a_i}\longrightarrow i$和$i \stackrel{b_i}{\longrightarrow} T$
对于每种收益$j$，拆点$j$和$j’$，分别表示共同种植在$A$或$B$的收益。对于$j$，连边$S \stackrel{c1_j}{\longrightarrow} j$和$j \stackrel{\infty}{\longrightarrow}i$；对于$j’$，连边$j’ \stackrel{c2_j}{\longrightarrow} T$和$i \stackrel{\infty}{\longrightarrow} j’$
最终答案为收益之和-最小割。
然后这个并不是这次想讲的重点。
这题其实还可以利用最大权闭合子图完成。考虑全部作物种植在$A$，然后调整至$B$。
对于每种作物$i$，点权为$b_i-a_i$；选择该点代表该作物调整到$B$种植。
对于每种收益$j$，拆点$j$和$j’$，表示共同种植在$A$或$B$的收益。对于$j$，点权为$-c1_j$，连边$i \longrightarrow j$；对于$j’$，点权为$c2_j$，连边$j’ \longrightarrow i$
实际意义很好理解，就不过多解释。
最终答案为种植在$A$的收益之和+最大权闭合子图。
最初接触文理分科模型的时候，我便试图使用最大权闭合子图解决。但因为无法处理二选一的情况而失败。但此处巧妙地处理了这种情况，用选与不选来代表种植在$A$还是$B$。
从这一点看来，似乎所有的文理分科模型都能通过此种方式，用最大权闭合子图来完成。
CODE
CODE(最小割) - Click Here
CODE(最大权闭合子图) - Click Here