Link
Question
给定一个 \(n\times m\) 的 01 矩阵,你可以把矩阵中的任意一个元素 01 翻转
需要最后的矩阵满足,每行 \(1\) 的个数有 \(A[i]\) 个,每列 \(1\) 的个数有 \(B[i]\) 个
Solution
这貌似是一道非常经典的费用流题目
我们建立 \(n\) 个行节点 ,\(m\) 个列节点,一个源点 \(s\) ,一个汇点 \(t\)
-
如果 \(a[i][j]==0\) 那么我们把 第 \(i\) 个行节点和第 \(j\) 个列节点之间建一条流量为 \(1\) 费用为 \(1\) 的边
-
如果 \(a[i][j]==1\) 那么我们把 第 \(i\) 个行节点和第 \(j\) 个列节点之间建一条流量为 \(1\) 费用为 \(-1\) 的边,(因为最后答案需要加上刚开始为 \(1\) 的点的数量,\(-1\) 用于撤销代价)
然后从源点 \(s\) 建一条到每个行节点 \(i\) ,容量为 \(A[i]\) ,费用为 \(0\) 的边
从每个列节点 \(j\) 到汇点 \(t\) ,建一条容量为 \(B[i]\) ,费用为 \(0\) 的边
最后的答案就是最小费用最大流+初始为 \(1\) 的 \(a\) 的数量
Code
#include<iostream>
#include<cstring>
#include<vector>
#include<limits>
using namespace std;
using LL = long long;
const int maxn = 1e4 + 5, maxm = 1e6 + 5;
template<typename cost_t>
struct MinCostMaxFlow{
const cost_t INF = numeric_limits<cost_t>::max() / 2;
int h[maxn], e[maxm], ne[maxm], idx;
cost_t f[maxm], w[maxm], d[maxn], incf[maxn];
int q[maxn], pre[maxn];
bool vis[maxn];
int V, S, T;
void init(int v, int s, int t){
for(int i = 0; i <= v; i++) h[i] = -1;
idx = 0;
V = v, S = s, T = t;
}
void add(int a, int b, cost_t c, cost_t d){
e[idx] = b, f[idx] = c, w[idx] = d, ne[idx] = h[a], h[a] = idx++;
e[idx] = a, f[idx] = 0, w[idx] = -d, ne[idx] = h[b], h[b] = idx++;
}
bool spfa(){
int hh = 0, tt = 0;
for(int i = 0; i <= V; i++){
d[i] = INF;
incf[i] = 0;
vis[i] = 0;
}
q[tt++] = S, d[S] = 0, incf[S] = INF;
while(hh != tt){
int t = q[hh++];
if (hh == maxn) hh = 0;
vis[t] = 0;
for(int i = h[t]; ~i; i = ne[i]){
int j = e[i];
if (f[i] && d[j] > d[t] + w[i]){
d[j] = d[t] + w[i];
incf[j] = min(incf[t], f[i]);
pre[j] = i;
if (!vis[j]){
vis[j] = 1;
q[tt++] = j;
if (tt == maxn) tt = 0;
}
}
}
}
return incf[T] > 0;
}
pair<cost_t, cost_t> EK(){
cost_t flow = 0, cost = 0;
while(spfa()){
cost_t t = incf[T];
flow += t, cost += d[T] * t;
for(int i = T; i != S; i = e[pre[i] ^ 1]){
f[pre[i]] -= t, f[pre[i] ^ 1] += t;
}
}
return {flow, cost};
}
};
MinCostMaxFlow<int> flow;
int main(){
freopen("E.in", "r", stdin);
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int n, m;
cin >> n >> m;
vector<vector<int> > c(n + 1, vector<int>(m + 1));
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> c[i][j];
}
}
int sum1 = 0, sum2 = 0;
vector<int> a(n + 1), b(m + 1);
for(int i = 1; i <= n; i++)
cin >> a[i], sum1 += a[i];
for(int i = 1; i <= m; i++)
cin >> b[i], sum2 += b[i];
if (sum1 != sum2){
cout << -1 << '\n';
return 0;
}
int s = 0, t = n + m + 1;
flow.init(n + m + 1, s, t);
for(int i = 1; i <= n; i++){
flow.add(s, i, a[i], 0);
}
for(int i = 1; i <= m; i++){
flow.add(i + n, t, b[i], 0);
}
int ans = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if (c[i][j] == 0){
flow.add(i, j + n, 1, 1);
}
else{
ans += 1;
flow.add(i, j + n, 1, -1);
}
}
}
auto [f, cost] = flow.EK();
if (f != sum1) cout << -1 << '\n';
else cout << ans + cost << '\n';
return 0;
}