直接糊一手线性规划对偶板板。
要求:
\[\min \sum A_i l_i + \sum B_i r_i
\]
\[\forall i, j, l_i + r_j \ge C_{i, j}
\]
\[l_i, r_i \ge 0
\]
\[l_i, r_i \in \mathbb{Z}
\]
可以证明 \(l_i, r_i\) 为整数的限制可以去掉,因为取到最优解时 \(l_i, r_i\) 一定顶着整数。
对偶相当于变量和限制互换,\(\min, \max\) 互换,不等式符号改变,变成:
\[\max \sum w_{i, j} C_{i, j}
\]
\[\sum\limits_j w_{i, j} \le A_i
\]
\[\sum\limits_i w_{i, j} \le B_j
\]
我去这不是费用流板板吗。\(w_{i, j}\) 相当于 \(i \to j'\) 的流量,\(C_{i, j}\) 相当于这条边的费用,\(\le A_i\) 和 \(\le B_j\) 的限制相当于和源点与汇点的边的容量。那么:
- 连边 \(S \to i\),容量为 \(A_i\),费用为 \(0\);
- 连边 \(i \to j'\),容量为 \(+\infty\),费用为 \(C_{i, j}\);
- 连边 \(j \to T\),容量为 \(B_i\),费用为 \(0\)。
跑一遍最大费用最大流即可。
最大费用最大流可以把费用全部取反跑最小费用最大流,最后把费用再取反。
code
// Problem: H - Security Camera 2
// Contest: AtCoder - AtCoder Beginner Contest 224
// URL: https://atcoder.jp/contests/abc224/tasks/abc224_h
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 110;
const int maxm = 1000100;
const ll inf = 0x3f3f3f3f3f3f3f3fLL;
ll n, m, a[maxn], b[maxn], c[maxn][maxn];
ll head[maxm], len = 1, S, T, ntot, id[maxn][2];
struct edge {
ll to, next, cap, flow, cost;
} edges[maxm];
inline void add_edge(ll u, ll v, ll c, ll f, ll co) {
edges[++len].to = v;
edges[len].next = head[u];
edges[len].cap = c;
edges[len].flow = f;
edges[len].cost = co;
head[u] = len;
}
struct MCMF {
ll d[maxm], cur[maxm];
bool vis[maxm];
inline void add(ll u, ll v, ll c, ll co) {
add_edge(u, v, c, 0, co);
add_edge(v, u, 0, 0, -co);
}
inline bool spfa() {
queue<int> q;
for (int i = 1; i <= ntot; ++i) {
d[i] = inf;
vis[i] = 0;
}
q.push(S);
vis[S] = 1;
d[S] = 0;
while (q.size()) {
int u = q.front();
q.pop();
vis[u] = 0;
for (int i = head[u]; i; i = edges[i].next) {
edge &e = edges[i];
if (d[e.to] > d[u] + e.cost && e.cap > e.flow) {
d[e.to] = d[u] + e.cost;
if (!vis[e.to]) {
vis[e.to] = 1;
q.push(e.to);
}
}
}
}
return d[T] < inf;
}
ll dfs(ll u, ll a, ll &cost) {
if (u == T || !a) {
return a;
}
vis[u] = 1;
ll flow = 0, f;
for (ll &i = cur[u]; i; i = edges[i].next) {
edge &e = edges[i];
if (!vis[e.to] && d[e.to] == d[u] + e.cost && e.cap > e.flow) {
if ((f = dfs(e.to, min(a, e.cap - e.flow), cost)) > 0) {
cost += f * e.cost;
e.flow += f;
edges[i ^ 1].flow -= f;
flow += f;
a -= f;
if (!a) {
break;
}
}
}
}
vis[u] = 0;
return flow;
}
inline pii solve() {
ll flow = 0, cost = 0;
while (spfa()) {
for (int i = 1; i <= ntot; ++i) {
cur[i] = head[i];
}
flow += dfs(S, inf, cost);
}
return mkp(flow, cost);
}
} solver;
void solve() {
scanf("%lld%lld", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
id[i][0] = ++ntot;
}
for (int i = 1; i <= m; ++i) {
scanf("%lld", &b[i]);
id[i][1] = ++ntot;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
scanf("%lld", &c[i][j]);
}
}
S = ++ntot;
T = ++ntot;
for (int i = 1; i <= n; ++i) {
solver.add(S, id[i][0], a[i], 0);
}
for (int i = 1; i <= m; ++i) {
solver.add(id[i][1], T, b[i], 0);
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
solver.add(id[i][0], id[j][1], inf, -c[i][j]);
}
}
pii ans = solver.solve();
printf("%lld\n", -ans.scd);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- Beginner Security AtCoder Contest Camerabeginner security atcoder contest contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 310 beginner atcoder contest 327