Educational Codeforces Round 160 (Rated for Div. 2) E. Matrix Problem（费用流）

原题链接：E. Matrix Problem

---

题目大意：

---

给出一个 $n$ 行 $m$ 列的 $0/1$ 矩阵，再给出一些限制条件：一个长为 $n$ 的数组 $a$，和一个长为 $m$ 的数组 $b$ 。

其中 $a_i$ 表示第 $i$ 行要有 恰好 $a_i$ 个 $1$ ， $b_j$ 表示第 $j$ 列要有 恰好 $b_j$ 个 $1$ ，保证 $1\le a_i\le m,1\le b_j\le n$ 。

你可以使用 任意多次 操作，将一个 $0$ 翻转成 $1$ ，或将 $1$ 翻转成 $0$ 。

问最少的操作次数是多少，才能使得这个矩阵满足以上 $a,b$ 限制，如果怎么操作都不能满足以上限制则输出 $-1$ 。

解题思路：

---

套路的，我们将行和列看成点，行为左部，列为右部，而每个位置 $(i,j)$ 的信息看成是一条 $i$ 和 $j$ 的边，这样我们的矩阵就会形成一张天然的二分图。

回到这一题，首先要是连 ${\sum }_{i=1}^n{a}_i\ne {\sum }_{i=1}^m{b}_i$ 了，那肯定无论如何都不会满足的，但只有这个条件是不够的，而且很容易找出反例，但我们可以先判掉，使得接下来 ${\sum }_{i=1}^n{a}_i={\sum }_{i=1}^m{b}_i$ ，方便后续讨论。

考虑全是 $0$ 我们怎么做，本质上就是每条边流量为 $1$ ，源点 $S\to [1,2,...,n]$ 连一条流量为 $a_i$ 的边，$[1,2,...,m]\to$ 汇点 $T$ 连一条流量为 $b_i$ 的边，然后跑一个最大流即可。

当我们发现最大流和 ${\sum }_{i=1}^n{a}_i$ 不等，那么显然无论如何操作也是不行的。

（其实本质上就是在做一个匹配的操作：点 $A$ 可以匹配 $a_i$ 个人，点 $B$ 可以匹配 $b_i$ 个人，看是否使得每个人都能匹配完全）

但是这一题是带操作次数的条件的，我们要最小操作次数，而且矩阵初始值也不是全为 $0$ ，这要怎么办？

首先考虑 $0$ 的位置的影响，如果某个地方的 $0$ 无论如何都要翻转为 $1$ 的，那么这个 $0$ 对操作的贡献是固定为 $1$ 的，我们直接操作就好。而其他无所谓的 $0$ 显然去操作只会让操作数变多，不优。

再考虑 $1$ 的位置的影响，无论如何我们都要把多余的 $1$ 给删掉，我们不妨先全部删除了，操作数就是 $1$ 的个数。再考虑哪些 $1$ 是可以作为选择的，然后反悔我们的删除操作，把这个 $1$ 加回来即可，这样对我们操作的贡献是为 $-1$ 的。

按照上面的转化，假设矩阵为 $g_{n,m}$ 那么：

• 先假设矩阵全为 $0$ ，统计 $1$ 的个数。
• 当 $g_{i,j}=1$ 时，我们添加边 $i\to j$ ，流量为 $1$，费用为 $-1$ （反悔）。
• 当 $g_{i,j}=0$ 时，我们添加边 $i\to j$ ，流量为 $1$，费用为 $1$ （固定）。
• $S$ 向 $i$ 连上流量为 $a_i$，费用为 $0$ 的边， $j$ 向 $T$ 连上流量为 $b_j$，费用为 $0$ 的边。
• 这里的 $i,j$ 分别指的是 左部 的点的编号和 右部 的点的编号。

如果最大流不为 ${\sum }_{i=1}^n{a}_i$ 说明不能匹配完全，输出 $-1$ 。

否则我们所需要的最小操作次数就是 ${\sum }_{i=1}^n{\sum }_{j=1}^m{g}_{i,j}+$ 最小费用 （固定 $+$ 反悔的和）。

代码使用的是 $Spfa+Dinic$ 的费用流。

时间复杂度：$O(n^3{m}^3)$ （伪多项式复杂度，可以通过）

AC代码：

#include <bits/stdc++.h>
using namespace std;using PII = pair<int, int>;
using i64 = long long;template<class Ty>
struct MCmaxFlow {const Ty INF = numeric_limits<Ty>::max();int S, T, n; Ty MF = 0, MC = 0;struct Edge {int v, nxt; Ty f, w;Edge() : Edge(0, 0, 0, 0) {};Edge(int v, int nxt, Ty f, Ty w) : v(v), nxt(nxt), f(f), w(w) {};};vector<Ty> dist;vector<int> cur, h;vector<bool> vis;vector<Edge> E;MCmaxFlow(int _) : n(_) { init(_); };void init(int _) {dist.resize(_ + 1);vis.resize(_ + 1);cur.resize(_ + 1);h.resize(_ + 1);E.resize(2);}void add(int u, int v, Ty f, Ty w) {E.emplace_back(v, h[u], f, w), h[u] = int(E.size()) - 1;}void addEdge(int u, int v, Ty f, Ty w) {add(u, v, f, w), add(v, u, 0, -w);}bool SPFA() {dist.assign(n + 1, INF);queue<int> que;dist[S] = 0, cur[S] = h[S];que.push(S);while (que.size()) {int u = que.front(); que.pop();vis[u] = false;for (int i = h[u]; i; i = E[i].nxt) {auto& [v, nxt, f, w] = E[i];if (f && dist[v] > dist[u] + w) {dist[v] = dist[u] + w;if (!vis[v]) {vis[v] = true;cur[v] = h[v];que.push(v);}}}}return dist[T] != INF;}Ty DFS(int u, Ty flow) {if (u == T) return flow;Ty last = flow;vis[u] = true;for (int i = cur[u]; i && last; i = E[i].nxt) {cur[u] = i;auto& [v, nxt, f, w] = E[i];if (f && !vis[v] && dist[v] == dist[u] + w) {Ty cost = DFS(v, min(f, last));if (!cost) dist[v] = INF;E[i].f -= cost, E[i ^ 1].f += cost;last -= cost;}}vis[u] = false;return flow - last;}void work() {while (SPFA()) {Ty flow = DFS(S, INF);MC += dist[T] * flow;MF += flow;}}
};void solve() {int n, m;cin >> n >> m;MCmaxFlow<int> G(n + m + 2);vector g(n + 1, vector<int>(m + 1));int ans = 0;// i -> j 连边for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {cin >> g[i][j];if (g[i][j]) {G.addEdge(i, n + j, 1, -1);++ans;} else {G.addEdge(i, n + j, 1, 1);}}}G.S = n + m + 1, G.T = G.S + 1;int suma = 0, sumb = 0;// S -> i 连边for (int i = 1; i <= n; ++i) {int x; cin >> x;G.addEdge(G.S, i, x, 0);suma += x;}// j -> T 连边for (int i = 1; i <= m; ++i) {int x; cin >> x;G.addEdge(n + i, G.T, x, 0);sumb += x;}//先特判 sum a != sum bif (suma != sumb) {cout << -1 << '\n';return;}G.work();//再特判 maxFlow != sum aif (G.MF != suma) {cout << -1 << '\n';return;}//答案就是 sum g[i][j] + minCostcout << ans + G.MC << '\n';
}signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int t = 1; //cin >> t;while (t--) solve();return 0;
}