ARC212B 题解
学网络流学的。文章末尾附带了一个精神正常的简略版本。
对于这种简单题，我们显然是可以用网络流的，对于
所以我觉得这题不应该是网络流，但是我觉得就是网络流。
于是我开始尝试手搓网络流。但是一想到数据范围是
所以我决定开始想更快的网络流做法是什么，但是我不知道网络流应该怎么写，也不知道预流推进应该怎么做。
因此我开始思考如何建模，我们发现可以把每行每列拆成一个点，每个操作就从行的点向列的点连边。容易发现这是一个二分图。因此很不难想到网络流，但是我并不会网络流。
于是我开始尝试手搓网络流。但是一想到数据范围是
所以我决定开始想更快的网络流做法是什么，但是我不知道网络流应该怎么写，也不知道预流推进应该怎么做。
因此我开始思考如何考虑代价，显然是很简单的，我们可以使用费用流来解决。
不过我并不知道费用流应该怎么写，所以我觉得这道题非常困难。
于是我开始尝试手搓费用流。但是一想到数据范围是
所以我决定开始想更快的费用流做法是什么，但是我不知道费用流应该怎么写，也不知道预流推进应该怎么做。
我已经破防了，我没有任何希望了。这是我第一次在自己有一堆 whk 作业没写完的时候开始打 ARC 比赛。
于是我决定先开始写代码，我开始寻找网络流的写法。
但是一想到数据范围是
不过我现在才知道我应该写的是费用流，我没记错的话费用流的复杂度和最大流有关系。所以我并不是很会这道题目。
因此我开始思考如何强制操作
不过我并不知道上下界费用流应该怎么写，所以我觉得这道题非常困难。
于是我开始尝试手搓费用流。但是一想到数据范围是
所以我决定开始想更快的费用流做法是什么，但是我不知道费用流应该怎么写，也不知道预流推进应该怎么做。
我开始考虑如何保证行和列的棋子个数相等。
我发现这是一道很简单的形式，因为相等这个条件很像流量守恒。这很显然可以使用网络流来做，我们去掉源点和汇点，跑无源汇上下界网络流，在对应的行和列之间连一条容量为
不过我并不知道无源汇上下界可行最小费用流应该怎么写，所以我觉得这道题非常困难。
于是我开始尝试手搓费用流。但是一想到数据范围是
所以我决定开始想更快的费用流做法是什么，但是我不知道费用流应该怎么写，也不知道预流推进应该怎么做。
因此我觉得我不应该思考费用流和 flow 相关的做法。
我认为 dp 是很没有前途的东西，于是我决定从我们建出来这张图开始找性质。
先假设我们找到了一个合法的流。不对！我不应该思考费用流应该怎么做！我不会费用流！
对于
所以我觉得 T1 不应该是网络流，但是我觉得就是网络流。
于是我开始尝试手搓网络流。但是一想到数据范围是
我们考虑从经过了第一个条件的边所对应的流。沿着这条流一直走下去，如果有多个选择就随便选一条。由于这条流到达的点肯定会有一条让这个流出去的点，因为要流量守恒。因此肯定有另外一条边指向了这个点。对于流上的每个点都是一样的。
因此我们猜测这个流是一个环。
但是一想到数据范围是
于是我开始尝试手搓网络流。发现如果只保留着一个流也不会有什么问题。
因此我们只需要找到一个包含了这条边的环即可。我们发现从这条边的终点跑一次到源点的最短路即可。
然后就做完了。
但是我还是不会网络流。
我真的不会网络流吗？
我真的不会网络流。
我学了两年还不会一个网络流吗？
我真的不会网络流。
想到这里，我的眼眶慢慢地被晶莹的眼泪覆盖，因为我的 whk 作业还没写完，而且明天是周一。我不禁开始后悔，可是世界上哪里有什么后悔药啊。
我想网络流的思想也是类似的，因为网络流就是通过建立反向边来起到“反悔”的一个作用。可是这世上哪里有什么反向边。
我痛定思痛，决定用仅存的斗志和理智把这道题写出来，然后
1 | |
喜提 WA。改完过了。
然后我就去写我的 whk 作业了。
考虑对于每行和每列写一个点，记作
我们发现保证两个点权值相等很像网络流的流量守恒，因此我们考虑直接把两个点合并成一个点，或者考虑从
但是进一步观察发现，如果一个流（必然是一个环，否则无法流量守恒）不经过操作
参考代码。