网络流24题
持续更新中，计划每两天更新一题
UPD1：期末考后再更QAQ
UPD2：多校期间随缘更新（大概每周日有空）QAQ
最小路径覆盖问题
首先有一个结论：最小不相交路径覆盖=顶点数-最大匹配，接下来进行说明
由于是一个DAG，因此它也是一个二分图
我们考虑最多的路径覆盖数为 $n$，也就是顶点数，考虑每次合并两个顶点，即进行一次匹配。每次匹配可以使当前的路径覆盖数 $-1$，所以答案就是顶点数-最大匹配
接下来就是输出方案的问题
在dfs的时候进行路径记录即可，直接模拟每次找增广路的过程即可
#include <bits/stdc++.h>
#define endl '\n'
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL,LL> PLL;
const int INF = 0x3f3f3f3f, N = 1e5 + 10, M = N << 1;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1);
inline int lowbit(int x) {return x & (-x);}
namespace Dinic{
//注意，建边的时候需要建流量为0的反向边
const int N = 1e5 + 10, M = N << 1;
const int INF = 0x3f3f3f3f;
int h[M], val[M], nex[M], w[M], tot;
int S, T; //源点与汇点
int dis[N];
int cur[N]; //当前弧优化
int to[N];
bool tag[N];
int n, m;
void init() {
memset(h, -1, sizeof h);
tot = 0;
}
void add(int a, int b, int c) {
val[tot] = b, w[tot] = c;
nex[tot] = h[a], h[a] = tot ++;
}
bool bfs() {
memset(dis, -1, sizeof dis);
dis[S] = 0;
queue<int> q;
q.push(S);
cur[S] = h[S];
while (!q.empty()) {
auto t = q.front(); q.pop();
for (int i = cur[t]; ~i; i = nex[i]) {
int v = val[i];
if (dis[v] != -1) continue;
if (w[i] <= 0) continue;
dis[v] = dis[t] + 1;
cur[v] = h[v];
q.push(v);
}
}
return dis[T] != -1;
}
int dinic(int x, int exp) {
//后者指流量限制
if (x == T) return exp;
int flow = 0, tmp = 0;
int i;
for (i = cur[x]; ~i; i = nex[i]) {
int v = val[i];
if (dis[v] == dis[x] + 1 && w[i] > 0) {
tmp = dinic(v, min(exp, w[i]));
if (!tmp) continue;
if (v > n && v != T) {
to[x] = v;
if (x != S) tag[v - n] = true;
}
exp -= tmp;
flow += tmp;
w[i] -= tmp;
w[i ^ 1] += tmp;
if (!exp) break;
}
}
cur[x] = i;
return flow;
}
int max_flow() {
int res = 0;
while (bfs()) res += dinic(S, INF);
for (int i = 1; i <= n; i ++ ) {
if (!tag[i]) {
int now = i;
cout << now << ' ';
while (to[now] && to[now] != T) {
cout << to[now] - n << ' ';
assert(to[now] - n > 0);
now = to[now] - n;
assert(now >= 0);
}
cout << endl;
}
}
return res;
}
}
using namespace Dinic;
inline void solve() {
init();
cin >> n >> m;
S = 0, T = 2 * n + 1;
while (m -- ) {
int a, b; cin >> a >> b;
add(a, b + n, 1), add(b + n, a, 0);
}
for (int i = 1; i <= n; i ++ ) {
add(S, i, 1), add(i, S, 0);
add(i + n, T, 1), add(T, i + n, 0);
}
int res = n - max_flow();
cout << res << endl;
}
signed main() {
#ifdef DEBUG
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
auto now = clock();
#endif
ios::sync_with_stdio(false), cin.tie(nullptr);
cout << fixed << setprecision(2);
// int T; cin >> T;
// while (T -- )
solve();
#ifdef DEBUG
cout << "============================" << endl;
cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
return 0;
}
CTSC1999家园 / 星际转移问题
这题的建图比较有意思
注意到数据范围很小，我们猜想答案应该不会很大
建立分层图，第i层的图表示第i天的状态，那么就有一种建图方式
以每个飞船的停留星球位置为一个点，来建图
那么当层数增加的时候，应该使当前层与上层产生什么关系呢？
- 由于周期性的走，所以对于每个飞船，将其上层所在的点和当前层所在的点连起来，流量为容量
- 由于人们可以待在一个太空站不走，所以将上一层的太空站和当前层的太空站连线
这是主要的建图思路，另外需要一个超级源点和超级汇点，分别连接每层的地球和月球
枚举答案，对于每个答案建图跑最大流，最大流即为可以搭载的人数，当可搭载人数满足要求即可
判断答案不存在可以用并查集检查地球和月球的连通性
#include <bits/stdc++.h>
#define endl '\n'
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL,LL> PLL;
const int INF = 0x3f3f3f3f, N = 1e5 + 10, M = 110;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1);
inline int lowbit(int x) {return x & (-x);}
int bot[M][M];
int r[M], g[M];
namespace Dinic{
//注意，建边的时候需要建流量为0的反向边
const int N = 1e5 + 10, M = N << 1;
int h[M], val[M], nex[M], w[M], tot;
int S, T; //源点与汇点
int dis[N];
void init() {
memset(h, -1, sizeof h);
tot = 0;
}
void add(int a, int b, int c) {
val[tot] = b, w[tot] = c;
nex[tot] = h[a], h[a] = tot ++;
}
bool bfs() {
memset(dis, -1, sizeof dis);
dis[S] = 0;
queue<int> q;
q.push(S);
while (!q.empty()) {
auto t = q.front(); q.pop();
for (int i = h[t]; ~i; i = nex[i]) {
int v = val[i];
if (dis[v] != -1) continue;
if (w[i] <= 0) continue;
dis[v] = dis[t] + 1;
q.push(v);
}
}
return dis[T] != -1;
}
int dinic(int x, int exp) {
//后者指流量限制
if (x == T || !exp) return exp;
int flow = 0, tmp = 0;
int i;
for (i = h[x]; ~i; i = nex[i]) {
int v = val[i];
if (dis[v] == dis[x] + 1 && w[i] > 0) {
tmp = dinic(v, min(exp, w[i]));
if (!tmp) continue;
exp -= tmp, flow += tmp;
w[i] -= tmp, w[i ^ 1] += tmp;
if (!exp) break;
}
}
if (!flow) dis[x] = -1;
return flow;
}
int max_flow() {
int res = 0;
while (bfs()) res += dinic(S, INT_MAX);
return res;
}
}
using namespace Dinic;
inline void solve() {
init();
int n, m, k; cin >> n >> m >> k;
S = 0, T = 14514;
vector<int> par(n + 10);
iota(par.begin() + 1, par.end(), 1);
function<int(int)> Find = [&](int x) {return x == par[x] ? x : par[x] = Find(par[x]);};
for (int i = 1; i <= m; i ++ ) {
cin >> g[i] >> r[i];
for (int j = 0; j < r[i]; j ++ ) {
cin >> bot[i][j];
if (bot[i][j] == 0) bot[i][j] = n + 1;
if (bot[i][j] == -1) bot[i][j] = n + 2;
if (j > 0) {
int x = Find(bot[i][j - 1]), y = Find(bot[i][j]);
if (x == y) continue;
par[x] = y;
}
}
}
if (Find(n + 1) != Find(n + 2)) {cout << 0 << endl; return ;}
auto calc = [&](int x, int p) {
return (n + 2) * x + p;
};
int t = 0, res = 0;
while (t < 550) {
add(S, calc(t, n + 1), INF);
add(calc(t, n + 1), S, 0);
add(calc(t, n + 2), T, INF);
add(T, calc(t, n + 2), 0);
if (t >= 1) {
for (int i = 1; i <= n + 2; i ++ ) {
add(calc(t - 1, i), calc(t, i), INF);
add(calc(t, i), calc(t - 1, i), 0);
}
for (int i = 1; i <= m; i ++ ) {
int x = bot[i][(t - 1) % r[i]];
int y = bot[i][t % r[i]];
add(calc(t - 1, x), calc(t, y), g[i]);
add(calc(t, y), calc(t - 1, x), 0);
}
}
res += max_flow();
// cout << res << endl;
if (res >= k) break;
t ++;
}
cout << t << endl;
}
signed main() {
#ifdef DEBUG
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
auto now = clock();
#endif
ios::sync_with_stdio(false), cin.tie(nullptr);
cout << fixed << setprecision(2);
// int T; cin >> T;
// while (T -- )
solve();
#ifdef DEBUG
cout << "============================" << endl;
cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
return 0;
}
太空飞行计划问题
这是一个最大权闭合子图问题，可以用最小割来解决
这里推荐胡伯涛的集训队论文《最小割模型在信息学竞赛中的应用》
关于最大权闭合子图用最小割解决的博客推荐这个
回到这题，这题的题意可以抽象为
给定两组点，左边组点权为正(实验奖励)，右边组为负(仪器费用)
要求选了左边的点时，必须得选与其相连的点
问选择若干个点，最大收益是多少
类似这种“选了一个点必须得选其后继的点，然后问最大收益”的问题，就叫做最大权闭合子图问题
这个是可以用最小割来解决的
具体的证明看我上面写的推荐博客和论文，这里不再赘述
结论就是：最大权闭合子图 = 所有正点权和-最小割
而最小割又是最大流，那么这题的建图就显而易见了
建立一个源点连接实验，边权为其实验收入；再建立一个汇点，让仪器与其连接，边权为花费，剩下的边连接情况不变，边权设置为无穷大
对于方案输出，容易看出最后与源点相连的点都是最大权闭合子图中的点
#include <bits/stdc++.h>
#define endl '\n'
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL,LL> PLL;
const int INF = 0x3f3f3f3f, N = 1e5 + 10;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1);
inline int lowbit(int x) {return x & (-x);}
int h[N], w[N], val[N], nex[N], tot;
int dep[N], cur[N];
int gl[N], gf[N];
int S, T;
void add(int a, int b, int c) {
val[tot] = b, w[tot] = c, nex[tot] = h[a], h[a] = tot ++;
val[tot] = a, w[tot] = 0, nex[tot] = h[b], h[b] = tot ++;
}
bool bfs() {
memset(dep, -1, sizeof dep);
dep[S] = 0;
queue<int> q;
q.push(S);
cur[S] = h[S];
while (!q.empty()) {
auto t = q.front(); q.pop();
for (int i = cur[t]; ~i; i = nex[i]) {
int v = val[i];
if (dep[v] != -1 || w[i] <= 0) continue;
dep[v] = dep[t] + 1;
cur[v] = h[v];
q.push(v);
}
}
return dep[T] != -1;
}
int dinic(int x, int lim) {
if (x == T) return lim;
int flow = 0, i;
for (i = cur[x]; ~i; i = nex[i]) {
int v = val[i];
if (dep[v] == dep[x] + 1 && w[i] > 0) {
int tmp = dinic(v, min(lim, w[i]));
if (tmp <= 0) continue;
lim -= tmp, flow += tmp;
w[i] -= tmp, w[i ^ 1] += tmp;
if (!lim) break;
}
}
cur[x] = i;
return flow;
}
int max_flow() {
int res = 0;
while (bfs()) res += dinic(S, INF);
return res;
}
inline void solve() {
memset(h, -1, sizeof h);
int m, n; cin >> m >> n;
int res = 0;
S = 0, T = n + m + 1;
getchar();
for (int i = 1; i <= m; i ++ ) {
string s;
getline(cin, s);
stringstream ss(s);
ss >> gl[i];
res += gl[i];
int x;
while (ss >> x) add(i, x + m, INF);
}
for (int i = 1; i <= n; i ++ ) cin >> gf[i];
for (int i = 1; i <= m; i ++ ) add(S, i, gl[i]);
for (int i = 1; i <= n; i ++ ) add(i + m, T, gf[i]);
res -= max_flow();
for (int i = 1; i <= m; i ++ ) if (dep[i] != -1) cout << i << ' ';
cout << endl;
for (int i = 1; i <= n; i ++ ) if (dep[i + m] != -1) cout << i << ' ';
cout << endl;
cout << res << endl;
}
signed main() {
#ifdef DEBUG
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
auto now = clock();
#endif
// ios::sync_with_stdio(false), cin.tie(nullptr);
// cout << fixed << setprecision(2);
// int T; cin >> T;
// while (T -- )
solve();
#ifdef DEBUG
cout << "============================" << endl;
cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
return 0;
}
试题库问题
一个比较常规的最大流问题
建图方式为，将源点和试题连线，流量为1，将试题类型和汇点链接，流量为要求的题目数，试题和试题类型的流量为1。
跑一遍最大流即可
方案输出也很简单，对每个试题类型，遍历与其相连的边，如果边权是正数说明最大流会跑过这里，输出即可。
#include <bits/stdc++.h>
#define endl '\n'
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL,LL> PLL;
const int INF = 0x3f3f3f3f, N = 1e5 + 10;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1);
inline int lowbit(int x) {return x & (-x);}
int h[N], w[N], nex[N], val[N], tot;
int dep[N], cur[N];
int S, T;
void add(int a, int b, int c) {
val[tot] = b, w[tot] = c, nex[tot] = h[a], h[a] = tot ++;
val[tot] = a, w[tot] = 0, nex[tot] = h[b], h[b] = tot ++;
}
bool bfs() {
memset(dep, -1, sizeof dep);
queue<int> q;
q.push(S);
dep[S] = 0;
cur[S] = h[S];
while (!q.empty()) {
auto t = q.front(); q.pop();
for (int i = h[t]; ~i; i = nex[i]) {
int v = val[i];
if (dep[v] != -1 || w[i] <= 0) continue;
dep[v] = dep[t] + 1;
cur[v] = h[v];
q.push(v);
}
}
return dep[T] != -1;
}
int dinic(int x, int lim) {
if (x == T) return lim;
int flow = 0, i;
for (i = cur[x]; ~i; i = nex[i]) {
int v = val[i];
if (dep[v] == dep[x] + 1 && w[i] > 0) {
int tmp = dinic(v, min(lim, w[i]));
if (tmp <= 0) continue;
lim -= tmp, flow += tmp;
w[i] -= tmp, w[i ^ 1] += tmp;
if (!lim) break;
}
}
cur[x] = i;
return flow;
}
inline void solve() {
memset(h, -1, sizeof h);
int n, m; cin >> n >> m;
vector<int> r(n + 1);
S = 0, T = n + m + 1;
int ans = 0;
for (int i = 1; i <= n; i ++ ) {
int x; cin >> x;
ans += x;
r[i] = x;
add(i + m, T, x);
}
for (int i = 1; i <= m; i ++ ) {
add(S, i, 1);
int num; cin >> num;
for (int j = 1; j <= num; j ++ ) {
int x; cin >> x;
add(i, x + m, 1);
}
}
while(bfs()) ans -= dinic(S, INF);
if (ans > 0) {cout << "No Solution!" << endl; return ;}
for (int i = 1; i <= n; i ++ ) {
vector<int> res;
for (int j = h[i + m]; ~j; j = nex[j]) {
int v = val[j];
if (v == T) continue;
if (w[j] > 0) res.push_back(v);
// if (res.size() == r[i]) break;
}
sort(res.begin(), res.end());
cout << i << ": ";
for (auto ite : res) cout << ite << ' ';
cout << endl;
}
}
signed main() {
#ifdef DEBUG
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
auto now = clock();
#endif
ios::sync_with_stdio(false), cin.tie(nullptr);
cout << fixed << setprecision(2);
// int T; cin >> T;
// while (T -- )
solve();
#ifdef DEBUG
cout << "============================" << endl;
cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
return 0;
}
最长不下降子序列问题
也是一个比较常规的问题，第一问是一个经典DP，第二问第三问用最大流解决，设第一问答案为 $len$
考虑建图，设 $dp[i]$ 为以i为开头的最长上升子序列的长度，将每个点拆成两个点 $i.a 与\ i,b$
- 当 $dp[i] = 1$ 时，将 $i.b$ 与汇点相连
- 当 $dp[i] = len$，将源点与 $i.a$ 相连
- 连接 $i.a$ 与 $i.b$
- 当 $i$ 可以由 $j$ 转移来时，连线 $j.b$ 与 $i.a$
主要易错点在拆点，如果不拆点，就无法体现出每个点只能被选一次这一特点，这个可以和二分图匹配类比
第二问将所有边权设为1即可，第三问只需要将1，n点相关的边权设为无穷即可
注意对1进行特判
#include <bits/stdc++.h>
#define endl '\n'
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL,LL> PLL;
const int INF = 0x3f3f3f3f, N = 1e6 + 10;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1);
inline int lowbit(int x) {return x & (-x);}
int h[N], val[N], nex[N], w[N], tot;
int dep[1010], cur[N];
int S, T;
void init() {
memset(h, -1, sizeof h);
tot = 0;
}
void add(int a, int b, int c) {
val[tot] = b, w[tot] = c, nex[tot] = h[a], h[a] = tot ++;
val[tot] = a, w[tot] = 0, nex[tot] = h[b], h[b] = tot ++;
}
bool bfs() {
memset(dep, -1, sizeof dep);
queue<int> q;
dep[S] = 0;
q.push(S);
cur[S] = h[S];
while (!q.empty()) {
auto t = q.front(); q.pop();
for (int i = h[t]; ~i; i = nex[i]) {
int v = val[i];
if (w[i] <= 0 || dep[v] != -1) continue;
dep[v] = dep[t] + 1;
cur[v] = h[v];
q.push(v);
}
}
return dep[T] != -1;
}
int dinic(int x, int lim) {
if (x == T) return lim;
int flow = 0, i;
for (i = cur[x]; ~i; i = nex[i]) {
int v = val[i];
if (dep[v] == dep[x] + 1 && w[i] > 0) {
int tmp = dinic(v, min(w[i], lim));
if (tmp <= 0) continue;
lim -= tmp, flow += tmp;
w[i] -= tmp, w[i ^ 1] += tmp;
if (!lim) break;
}
}
cur[x] = i;
return flow;
}
int max_flow() {
int res = 0;
while (bfs()) res += dinic(S, INF);
return res;
}
inline void solve() {
int n; cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i ++ ) cin >> a[i];
S = 0, T = 2 * n + 1;
vector<int> dp(n + 1);
int mx = 0;
for (int i = n; i; i -- ) {
dp[i] = max(dp[i], 1);
mx = max(dp[i], mx);
for (int j = i - 1; j; j -- ) if (a[j] <= a[i]) dp[j] = max(dp[j], dp[i] + 1);
}
cout << mx << endl;
init();
for (int i = 1; i <= n; i ++ ) {
add(i, i + n, 1);
if (dp[i] == mx) add(S, i, 1);
if (dp[i] == 1) add(i + n, T, 1);
for (int j = 1; j < i; j ++ ) if (a[j] <= a[i] && dp[j] == dp[i] + 1) add(j + n, i, 1);
}
cout << max_flow() << endl;
if (n == 1) {
cout << 1 << endl;
return ;
}
init();
for (int i = 1; i <= n; i ++ ) {
add(i, i + n, 1);
if (dp[i] == mx) {
if (i == 1) add(S, i, INT_MAX), add(i, i + n, INT_MAX);
else add(S, i, 1);
}
if (dp[i] == 1) {
if (i == n) add(i + n, T, INT_MAX), add(i, i + n, INT_MAX);
else add(i + n, T, 1);
}
for (int j = 1; j < i; j ++ ) if (a[j] <= a[i] && dp[j] == dp[i] + 1) add(j + n, i, 1);
}
cout << max_flow() << endl;
}
signed main() {
#ifdef DEBUG
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
auto now = clock();
#endif
ios::sync_with_stdio(false), cin.tie(nullptr);
cout << fixed << setprecision(2);
// int T; cin >> T;
// while (T -- )
solve();
#ifdef DEBUG
cout << "============================" << endl;
cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
return 0;
}
圆桌问题
很常规的一题，没啥需要特别注意的，直接说建图
左边n个点表示单位，右边m个点表示圆桌
源点对每个单位连边，流量为单位人数
每个圆桌对汇点连边，流量为圆桌容量
每个单位对每个圆桌连边，流量为1
直接跑最大流就行了，方案输出和上面的试题库类似
#include <bits/stdc++.h>
#define endl '\n'
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL,LL> PLL;
const int INF = 0x3f3f3f3f, N = 1e5 + 10;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1);
inline int lowbit(int x) {return x & (-x);}
int h[N], val[N], nex[N], w[N], tot;
int dep[1010], cur[N];
int S, T;
void add(int a, int b, int c) {
val[tot] = b, w[tot] = c, nex[tot] = h[a], h[a] = tot ++;
val[tot] = a, w[tot] = 0, nex[tot] = h[b], h[b] = tot ++;
}
bool bfs() {
memset(dep, -1, sizeof dep);
queue<int> q;
q.push(S);
dep[S] = 0;
cur[S] = h[S];
while (!q.empty()) {
auto t = q.front(); q.pop();
for (int i = cur[t]; ~i; i = nex[i]) {
int v = val[i];
if (dep[v] != -1 || w[i] <= 0) continue;
dep[v] = dep[t] + 1;
cur[v] = h[v];
q.push(v);
}
}
return dep[T] != -1;
}
int dinic(int x, int lim) {
if (x == T) return lim;
int flow = 0, i;
for (i = cur[x]; ~i; i = nex[i]) {
int v = val[i];
if (dep[v] == dep[x] + 1 && w[i] > 0) {
int tmp = dinic(v, min(lim, w[i]));
if (tmp <= 0) continue;
lim -= tmp, flow += tmp;
w[i] -= tmp, w[i ^ 1] += tmp;
if (!lim) break;
}
}
cur[x] = i;
return flow;
}
inline void solve() {
memset(h, -1, sizeof h);
int n, m; cin >> n >> m;
S = 0, T = n + m + 1;
int res = 0;
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= m; j ++ ) add(i, j + n, 1);
int x; cin >> x;
res += x;
add(S, i, x);
}
for (int i = 1; i <= m; i ++ ) {
int x; cin >> x;
add(i + n, T, x);
}
while (bfs()) res -= dinic(S, INF);
if (res > 0) {cout << 0 << endl; return ;}
cout << 1 << endl;
vector<vector<int>> ans(n + 1);
for (int i = 1; i <= m; i ++ ) {
for (int j = h[i + n]; ~j; j = nex[j]) {
int v = val[j];
if (v == T) continue;
assert(v <= n);
if (w[j] > 0) ans[v].push_back(i);
}
}
for (int i = 1; i <= n; i ++ ) {
for (auto ite : ans[i]) cout << ite << ' ';
cout << endl;
}
}
signed main() {
#ifdef DEBUG
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
auto now = clock();
#endif
ios::sync_with_stdio(false), cin.tie(nullptr);
cout << fixed << setprecision(2);
// int T; cin >> T;
// while (T -- )
solve();
#ifdef DEBUG
cout << "============================" << endl;
cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
return 0;
}
方格取数问题
假如对每个可连线的点建图然后跑最大流，那么图的规模是 $n^4$ 的，显然不行
所以我们考虑，先选择所有的点，然后删去一些点，于是我们想到最小割
由题意，我们把方格图黑白染色，然后将源点和黑色连边，流量为其权值，然后将白色和汇点连边，流量为其权值，相邻的格子连边，权值为无穷大，这样保证最小割的时候不会把这个边割掉，然后跑一边最大流就行了
#include <bits/stdc++.h>
#define endl '\n'
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL,LL> PLL;
const int INF = 0x3f3f3f3f, N = 2e5 + 10;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1);
inline int lowbit(int x) {return x & (-x);}
int h[N], val[N], w[N], nex[N], tot;
int dep[N], cur[N];
int S, T;
void add(int a, int b, int c) {
val[tot] = b, w[tot] = c, nex[tot] = h[a], h[a] = tot ++;
val[tot] = a, w[tot] = 0, nex[tot] = h[b], h[b] = tot ++;
}
bool bfs() {
memset(dep, -1, sizeof dep);
queue<int> q;
q.push(S);
dep[S] = 0;
cur[S] = h[S];
while (!q.empty()) {
auto t = q.front(); q.pop();
for (int i = cur[t]; ~i; i = nex[i]) {
int v = val[i];
if (dep[v] != -1 || w[i] <= 0) continue;
dep[v] = dep[t] + 1;
cur[v] = h[v];
q.push(v);
}
}
return dep[T] != -1;
}
int dinic(int x, int lim) {
if (x == T) return lim;
int flow = 0, i;
for (i = cur[x]; ~i; i = nex[i]) {
int v = val[i];
if (dep[v] == dep[x] + 1 && w[i] > 0) {
int tmp = dinic(v, min(lim, w[i]));
if (tmp <= 0) continue;
lim -= tmp, flow += tmp;
w[i] -= tmp, w[i ^ 1] += tmp;
if (!lim) break;
}
}
cur[x] = i;
return flow;
}
int max_flow() {
int res = 0;
while (bfs()) res += dinic(S, INF);
return res;
}
inline void solve() {
memset(h, -1, sizeof h);
int n, m; cin >> n >> m;
S = 0, T = n * m + 1;
int res = 0;
auto getIdx = [&](int x, int y) {
return (x - 1) * m + y;
};
vector<int> dx = {0, 1, 0, -1};
vector<int> dy = {1, 0, -1, 0};
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= m; j ++ ) {
int x; cin >> x;
res += x;
if ((i + j) & 1) add(S, getIdx(i, j), x);
else add(getIdx(i, j), T, x);
if ((i + j) & 1) {
for (int k = 0; k < 4; k ++ ) {
int nx = i + dx[k], ny = j + dy[k];
if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
add(getIdx(i, j), getIdx(nx, ny), INF);
}
}
}
}
cout << res - max_flow() << endl;
}
signed main() {
#ifdef DEBUG
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
auto now = clock();
#endif
ios::sync_with_stdio(false), cin.tie(nullptr);
cout << fixed << setprecision(2);
// int T; cin >> T;
// while (T -- )
solve();
#ifdef DEBUG
cout << "============================" << endl;
cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
return 0;
}
