原题链接:E. Matrix Problem
题目大意:
给出一个 n n n 行 m m m 列的 0 / 1 0/1 0/1 矩阵,再给出一些限制条件:一个长为 n n n 的数组 a a a,和一个长为 m m m 的数组 b b b 。
其中 a i a_{i} ai 表示第 i i i 行要有 恰好 a i a_{i} ai 个 1 1 1 , b j b_{j} bj 表示第 j j j 列要有 恰好 b j b_{j} bj 个 1 1 1 ,保证 1 ≤ a i ≤ m , 1 ≤ b j ≤ n 1 \leq a_{i} \leq m,1 \leq b_{j} \leq n 1≤ai≤m,1≤bj≤n 。
你可以使用 任意多次 操作,将一个 0 0 0 翻转成 1 1 1 ,或将 1 1 1 翻转成 0 0 0 。
问最少的操作次数是多少,才能使得这个矩阵满足以上 a , b a,b a,b 限制,如果怎么操作都不能满足以上限制则输出 − 1 -1 −1 。
解题思路:
套路的,我们将行和列看成点,行为左部,列为右部,而每个位置 ( i , j ) (i,j) (i,j) 的信息看成是一条 i i i 和 j j j 的边,这样我们的矩阵就会形成一张天然的二分图。
回到这一题,首先要是连 ∑ i = 1 n a i ≠ ∑ i = 1 m b i \sum_{i=1}^{n} a_{i} \neq \sum_{i=1}^{m} b_{i} ∑i=1nai=∑i=1mbi 了,那肯定无论如何都不会满足的,但只有这个条件是不够的,而且很容易找出反例,但我们可以先判掉,使得接下来 ∑ i = 1 n a i = ∑ i = 1 m b i \sum_{i=1}^{n} a_{i} = \sum_{i=1}^{m} b_{i} ∑i=1nai=∑i=1mbi ,方便后续讨论。
考虑全是 0 0 0 我们怎么做,本质上就是每条边流量为 1 1 1 ,源点 S → [ 1 , 2 , . . . , n ] S \rightarrow [1,2,...,n] S→[1,2,...,n] 连一条流量为 a i a_{i} ai 的边, [ 1 , 2 , . . . , m ] → [1,2,...,m] \rightarrow [1,2,...,m]→ 汇点 T T T 连一条流量为 b i b_{i} bi 的边,然后跑一个最大流即可。
当我们发现最大流和 ∑ i = 1 n a i \sum_{i=1}^{n} a_{i} ∑i=1nai 不等,那么显然无论如何操作也是不行的。
(其实本质上就是在做一个匹配的操作:点 A A A 可以匹配 a i a_{i} ai 个人,点 B B B 可以匹配 b i b_{i} bi 个人,看是否使得每个人都能匹配完全)
但是这一题是带操作次数的条件的,我们要最小操作次数,而且矩阵初始值也不是全为 0 0 0 ,这要怎么办?
首先考虑 0 0 0 的位置的影响,如果某个地方的 0 0 0 无论如何都要翻转为 1 1 1 的,那么这个 0 0 0 对操作的贡献是固定为 1 1 1 的,我们直接操作就好。而其他无所谓的 0 0 0 显然去操作只会让操作数变多,不优。
再考虑 1 1 1 的位置的影响,无论如何我们都要把多余的 1 1 1 给删掉,我们不妨先全部删除了,操作数就是 1 1 1 的个数。再考虑哪些 1 1 1 是可以作为选择的,然后反悔我们的删除操作,把这个 1 1 1 加回来即可,这样对我们操作的贡献是为 − 1 -1 −1 的。
按照上面的转化,假设矩阵为 g n , m g_{n,m} gn,m 那么:
- 先假设矩阵全为 0 0 0 ,统计 1 1 1 的个数。
- 当 g i , j = 1 g_{i,j}=1 gi,j=1 时,我们添加边 i → j i \rightarrow j i→j ,流量为 1 1 1,费用为 − 1 -1 −1 (反悔)。
- 当 g i , j = 0 g_{i,j}=0 gi,j=0 时,我们添加边 i → j i \rightarrow j i→j ,流量为 1 1 1,费用为 1 1 1 (固定)。
- S S S 向 i i i 连上流量为 a i a_{i} ai,费用为 0 0 0 的边, j j j 向 T T T 连上流量为 b j b_{j} bj,费用为 0 0 0 的边。
- 这里的 i , j i,j i,j 分别指的是 左部 的点的编号和 右部 的点的编号。
如果最大流不为 ∑ i = 1 n a i \sum_{i=1}^{n} a_{i} ∑i=1nai 说明不能匹配完全,输出 − 1 -1 −1 。
否则我们所需要的最小操作次数就是 ∑ i = 1 n ∑ j = 1 m g i , j + \sum_{i=1}^{n}\sum_{j=1}^{m}g_{i,j}+ ∑i=1n∑j=1mgi,j+ 最小费用 (固定 + + + 反悔的和)。
代码使用的是 S p f a + D i n i c Spfa+Dinic Spfa+Dinic 的费用流。
时间复杂度: O ( n 3 m 3 ) O(n^{3}m^{3}) O(n3m3) (伪多项式复杂度,可以通过)
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 b
if (suma != sumb) {
cout << -1 << '\n';
return;
}
G.work();
//再特判 maxFlow != sum a
if (G.MF != suma) {
cout << -1 << '\n';
return;
}
//答案就是 sum g[i][j] + minCost
cout << 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;
}