小D的剑阵
题意：
有 $n$ 个物品，选第 $i$ 个物品会得到 $w_i$ 的贡献。
有 $q$ 个约束，每个约束形如 $x$ $y$ $v_0$ $v_1$ $v_2$
$x$ 和 $y$ 表示两个物品编号，同时选中可以获得额外 $v_0$ 的贡献，同时不选可以获得额外 $v_1$ 的贡献，只选择一个会扣除 $v_2$ 的贡献。
问你怎样选能够获得最大贡献。
$w$ $v$ 都是偶数。
有约束存在，考虑用网络流，这就是一个经典的最小割模型，把全部有的贡献加起来，然后选矛盾最小的贡献割掉就是答案了。
每一组矛盾就是一个割，把这些矛盾的式子列出来然后建图。
假设连 $s$ 表示不选，$t$ 表示选。
$a + c = w_x + w_y + v_0$ （都不选，损失掉两个原基础贡献和 $v_0$）
$b + d = v_1$ （都选，损失掉都不选的贡献 $v_1$）
$a + e + d = w_x + v_0 + v_1 + v_2$ （选 $y$ 不选 $x$ 损失掉 $w_x$ 和所有 $v$）
$c + f + b = w_y + v_0 + v_1 + v_2$ （选 $x$ 不选 $y$ 损失掉 $w_y$ 和所有 $v$）
发现化出来有个 $e + f = v_0 + v_1 + 2 \times v_2$。
这个与 $w$ 无关。
所以
$e = f = \frac{v_0 + v_1}{2} + v_2$
$b = d = \frac{v_1}{2}$
$a = w_x + \frac{v_0}{2}$
$c = w_y + \frac{v_0}{2}$
答案就是把所有 $w_i$，所有约束的 $v_0$ $v_1$ 加起来，再减去最小割。
1 |
|
文理分科
题意：
文理分科是一件很纠结的事情！（虽然看到这个题目的人肯定都没有纠
结过）
小$P$所在的班级要进行文理分科。他的班级可以用一个$n*m$的矩阵进行
描述，每个格子代表一个同学的座位。每位同学必须从文科和理科中选择
一科。同学们在选择科目的时候会获得一个满意值。满意值按如下的方式
得到：
1．如果第$i$行第$j$列的同学选择了文科，则他将获得$art[i][j]$的满意值，如
果选择理科，将得到$science[i][j]$的满意值。
2．如果第$i$行第$j$列的同学选择了文科，并且他相邻（两个格子相邻当且
仅当它们拥有一条相同的边）的同学全部选择了文科，则他会更开
心，所以会增加$same_art[i][j]$的满意值。
3．如果第$i$行第$j$列的同学选择了理科，并且他相邻的同学全部选择了理
科，则增加$same_science[i][j]$的满意值。
小$P$想知道，大家应该如何选择，才能使所有人的满意值之和最大。请
告诉他这个最大值。
也是一道把所有贡献加起来，把最小矛盾割掉求贡献的题。
建图类似上一题，只不过这题的约束是多个点。
连 $s$ 表示选文，连 $t$ 表示选理。
我们考虑每个点拆两个出来，一个连 $s$ 和四周围的人的点，另一个连 $t$ 和四周围的人的点。
差不多是下图这个样子。
左边连 $s$ 的边容量为 $art$，右边连 $t$ 的边容量为 $science$，左边连 $s$ 的出来的点的边容量为 $art_same$，右边连 $t$ 的出来的点的边容量为 $science_same$，红色的边容量为 $inf$。
答案是全部贡献 - 最小割。
1 |
|