「题目汇总」网络流 24 题

本蒟蒻在此祝 dalao 们新年新进步，新年新 AK！

此处为网络流 24 题的题解汇总。

传送门：LOJ、洛谷。

注：机器人路径规划问题咕咕了。搭配飞行员、软件补丁 和 负载平衡 太水不写。

Todo

机器人路径规划 Solution

餐巾计划

题意

传送门：洛谷 P1251 - 餐巾计划问题、LOJ 6008 - 餐巾计划。

有 \(n\) 天。第 \(i\) 天要 \(r_i\) 块餐巾。买一块餐巾 \(P\) 分，快洗部洗一块要 \(M\) 天，\(F\) 分钱；慢洗部洗一块要 \(N\) 天，\(S\) 分钱。允许延期送洗。问最少花多少钱。

解法

把餐巾视为流量，代价视为费用。对于每一天，拆成早上和晚上，即 \(x\) 和 \(x’\)。

每天晚上将获得 \(r_i\) 块脏餐巾。所以连接 \(S \xrightarrow{r_i, 0} x'\)；

每天早上要使用 \(r_i\) 块干净餐巾。所以连接 \(x \xrightarrow{r_i, 0} T\)；

每天草上可以买任意多块餐巾。所以连接 \(S \xrightarrow{+\infty, P} x\)；

快洗部用 \(M\) 天将任意多块餐巾洗干净。所以连接 \(i \xrightarrow{+\infty, F} (i + M)\)；

快洗部用 \(N\) 天将任意多块餐巾洗干净。所以连接 \(i \xrightarrow{+\infty, S} (i + N)\)。

其中 \(x \xrightarrow{a, b} y\) 代表从 \(x\) 向 \(y\) 连接一条流量为 \(a\)，费用为 \(b\) 的有向边。

代码

LOJ 和 洛谷 的输入格式不一样。好坑~

LOJ Ver.

#include <cstdio>
#include <cstring>
#include <queue>

typedef long long ll;
const int N = 4e3 + 34, M = 2e4 + 42, INF = 0x3f3f3f3f;
struct edge {
    int to, next, w, c;
} e[M << 1];
int head[N], cnt = 1;
void addedge(int x, int y, int z, int w) {
    e[++cnt] = (edge){y, head[x], z, w};
    head[x] = cnt;
    e[++cnt] = (edge){x, head[y], 0, -w};
    head[y] = cnt;
}

void ek(int s, int t, int& mflow, ll& mcost) {
    int dis[N], vis[N], flow[N], pre[N];
    std::queue<int> q;
    mflow = mcost = 0;
    while (1) {
        memset(dis, 0x3f, sizeof dis);
        q.push(s);
        dis[s] = 0;
        flow[s] = INF;
        while (!q.empty()) {
            int pos = q.front();
            vis[pos] = 0;
            q.pop();
            for (int i = head[pos]; i; i = e[i].next) {
                int nx = e[i].to;
                if (e[i].w && dis[nx] > dis[pos] + e[i].c) {
                    dis[nx] = dis[pos] + e[i].c;
                    flow[nx] = std::min(flow[pos], e[i].w);
                    pre[nx] = i;
                    if (!vis[nx]) {
                        vis[nx] = 1;
                        q.push(nx);
                    }
                }
            }
        }
        if (dis[t] == INF) return;
        for (int i = pre[t]; i; i = pre[e[i ^ 1].to]) {
            e[i].w -= flow[t];
            e[i ^ 1].w += flow[t];
        }
        mflow += flow[t];
        mcost += dis[t] * flow[t];
    }
}

int n, x, a, b, c, d, _;
ll y;

int main() {
    scanf("%d%d%d%d%d%d", &n, &a, &b, &c, &d, &_);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &x);
        addedge(1, i + 2, x, 0);
        addedge(n + i + 2, 2, x, 0);
    }
    for (int i = 1; i <= n; i++) {
        addedge(1, i + n + 2, INF, a);
        if (i < n) addedge(i + 2, i + 3, INF, 0);
        if (i + b <= n) addedge(i + 2, i + n + b + 2, INF, c);
        if (i + d <= n) addedge(i + 2, i + n + d + 2, INF, _);
    }
    ek(1, 2, x, y);
    printf("%lld", y);
}

洛谷 Ver.

#include <cstdio>
#include <cstring>
#include <queue>

typedef long long ll;
const int N = 4e3 + 34, M = 2e4 + 42, INF = 0x3f3f3f3f;
struct edge {
    int to, next, w, c;
} e[M << 1];
int head[N], cnt = 1;
void addedge(int x, int y, int z, int w) {
    e[++cnt] = (edge){y, head[x], z, w};
    head[x] = cnt;
    e[++cnt] = (edge){x, head[y], 0, -w};
    head[y] = cnt;
}

void ek(int s, int t, int& mflow, ll& mcost) {
    int dis[N], vis[N], flow[N], pre[N];
    std::queue<int> q;
    mflow = mcost = 0;
    while (1) {
        memset(dis, 0x3f, sizeof dis);
        q.push(s);
        dis[s] = 0;
        flow[s] = INF;
        while (!q.empty()) {
            int pos = q.front();
            vis[pos] = 0;
            q.pop();
            for (int i = head[pos]; i; i = e[i].next) {
                int nx = e[i].to;
                if (e[i].w && dis[nx] > dis[pos] + e[i].c) {
                    dis[nx] = dis[pos] + e[i].c;
                    flow[nx] = std::min(flow[pos], e[i].w);
                    pre[nx] = i;
                    if (!vis[nx]) {
                        vis[nx] = 1;
                        q.push(nx);
                    }
                }
            }
        }
        if (dis[t] == INF) return;
        for (int i = pre[t]; i; i = pre[e[i ^ 1].to]) {
            e[i].w -= flow[t];
            e[i ^ 1].w += flow[t];
        }
        mflow += flow[t];
        mcost += dis[t] * flow[t];
    }
}

int n, x, a, b, c, d, _;
ll y;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &x);
        addedge(1, i + 2, x, 0);
        addedge(n + i + 2, 2, x, 0);
    }
    scanf("%d%d%d%d%d", &a, &b, &c, &d, &_);
    for (int i = 1; i <= n; i++) {
        addedge(1, i + n + 2, INF, a);
        if (i < n) addedge(i + 2, i + 3, INF, 0);
        if (i + b <= n) addedge(i + 2, i + n + b + 2, INF, c);
        if (i + d <= n) addedge(i + 2, i + n + d + 2, INF, _);
    }
    ek(1, 2, x, y);
    printf("%lld", y);
}

星际转移

题意

传送门：洛谷 P2754 - 家园、LOJ 6015 - 星际转移。

有 $n+2~([-1, n]) $ 站和 \(m\) 趟班车，每趟班车会在一个站点集合 \(v_{i,0} \sim v_{i, c_i-1}\) 里轮流转。第 \(i\) 趟班车可以坐 \(h_i\) 人，最开始 \(0\) 号站有 \(k\) 个人，问最快要多久所有人都转移到 \(-1\) 站。

题解

考虑按时间拆点。令 \(t\) 时刻的 \(i\) 号站为 \((t, i)\)。

第 \(0\) 时刻，\(0\) 站有 \(k\) 个人，所以 \(S \xrightarrow k (0, 0)\)。

以后的每一时刻，每个站的人可以选择待在这个站，也可以选择坐车。即 \((t, i) \xrightarrow1 (t+1, i)\) 和 \((t, v_{i, t \bmod c_i}) \xrightarrow1 (t+1, v_{i, (t+1) \bmod c_i})\)。

然后求 \((0, 0)\) 到 \((t, -1)\) 的最大流。如果达到了 \(k\) 就输出，否则继续。

注意加边求最大流不需要清空流量。

代码

代码

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>

const int N = 1e3 + 31, M = 4e4 + 44, K = 55, INF = 0x3f3f3f3f;
struct edge {
    int to, next, w;
} e[M << 1];
int head[N], cnt = 1;
void addedge(int x, int y, int z) {
    e[++cnt] = (edge){y, head[x], z}, head[x] = cnt;
    e[++cnt] = (edge){x, head[y], 0}, head[y] = cnt;
}

int lv[N];
int bfs(int s, int t) {
    memset(lv, 0, sizeof lv);
    std::queue<int> q;
    lv[s] = 1;
    q.push(s);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = head[x]; i; i = e[i].next) {
            int nx = e[i].to;
            if (!e[i].w || lv[nx]) continue;
            lv[nx] = lv[x] + 1;
            q.push(nx);
        }
    }
    return lv[t];
}
int dfs(int s, int t, int f) {
    if (s == t) return f;
    int r = 0;
    for (int i = head[s]; f && i; i = e[i].next) {
        int nx = e[i].to;
        if (!e[i].w || lv[nx] != lv[s] + 1) continue;
        int tmp = dfs(nx, t, std::min(f, e[i].w));
        r += tmp, f -= tmp;
        e[i].w -= tmp, e[i ^ 1].w += tmp;
    }
    if (!r) lv[s] = 0;
    return r;
}
int dinic(int s, int t) {
    int ret = 0;
    while (bfs(s, t)) ret += dfs(s, t, INF);
    return ret;
}

int par[K];
int f(int x) { return par[x] ? par[x] = f(par[x]) : x; }
inline void g(int x, int y) {
    if ((x = f(x)) != (y = f(y))) par[x] = y;
}

int n, m, k, x, y, ans, c[K], h[K];
std::vector<int> v[K];
inline int id(int t, int i) { return t * n + i + 1; }
int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= m; i++) {
        for (scanf("%d%d", h + i, &x), c[i] = x; x--;) {
            scanf("%d", &y);
            v[i].push_back(y += 2);
            g(v[i].front(), v[i].back());
        }
    }
    if (f(1) != f(2)) return puts("0"), 0;
    n += 2;
    addedge(1, 3, k);
    for (int t = 1;; t++) {
        for (int i = 1; i <= n; i++) addedge(id(t - 1, i), id(t, i), INF);
        for (int j = 1; j <= m; j++)
            addedge(id(t - 1, v[j][(t - 1 + c[j]) % c[j]]), id(t, v[j][t % c[j]]), h[j]);
        if ((ans += dinic(1, id(t, 1))) == k) {
            return !printf("%d", t);
        }
    }
}

太空飞行计划

题意

传送门：洛谷 P2762 - 太空飞行计划问题、LOJ 6001 - 太空飞行计划。

\(n\) 个实验，\(m\) 种器材。实验 \(i\) 需要使用 \(R_i\) 这个集合中的仪器，价值是 \(p_i\)。仪器 \(i\) 的代价是 \(c_i\)，可以多次使用。问如何实验可以获利最大。

解法

最大权闭合子图模板题。

\(S \xrightarrow{p_i} \text{实验}_i\)，\(\forall j \in R_i, \text{实验}_i \xrightarrow{+\infty} \text{仪器}_j\)，\(\text{仪器}_i \xrightarrow{c_i} T\) 即可。

答案是 所有正权边的和减去最小割。

答案为 Dinic 中最后一次求 bfs 时仍有 level 的点。（其它点被鸽割掉了）

代码

LOJ 不允许行末空格……

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

const int N = 2e2 + 22, M = 1e4 + 41;

struct edge {
    int to, next, w;
} e[M << 1];
int head[N], cnt = 1;
void addedge(int x, int y, int z) {
    e[++cnt] = (edge){y, head[x], z}, head[x] = cnt;
    e[++cnt] = (edge){x, head[y], 0}, head[y] = cnt;
}

int level[N];
bool bfs(int s, int t) {
    memset(level, 0, sizeof level);
    std::queue<int> q;
    level[s] = 1;
    q.push(s);
    while (!q.empty()) {
        int pos = q.front();
        q.pop();
        for (int i = head[pos]; i; i = e[i].next) {
            int nx = e[i].to;
            if (level[nx] || !e[i].w) continue;
            level[nx] = level[pos] + 1;
            q.push(nx);
        }
    }
    return level[t];
}
int dfs(int s, int t, int flow) {
    if (s == t) return flow;
    int ret = 0;
    for (int i = head[s]; flow && i; i = e[i].next) {
        int nx = e[i].to;
        if (level[nx] == level[s] + 1 && e[i].w) {
            int tmp = dfs(nx, t, std::min(flow, e[i].w));
            flow -= tmp;
            ret += tmp;
            e[i].w -= tmp;
            e[i ^ 1].w += tmp;
        }
    }
    return ret;
}
int dinic(int s, int t) {
    int ret = 0;
    while (bfs(s, t)) ret += dfs(s, t, 0x3f3f3f3f);
    return ret;
}

int n, m, x, s, t, sum, f;
char buf[' '];

int main() {
    scanf("%d%d", &n, &m);
    s = n + m + 1, t = n + m + 2;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &x);
        addedge(s, i, x);
        sum += x;
        std::cin.getline(buf, ' ');
        for (int j = 0; ~sscanf(buf + j, "%d", &x); j++) {
            j += !x;
            addedge(i, n + x, 0x3f3f3f3f);
            for (j += !x; x; x /= 10) j++;
        }
    }
    for (int i = 1; i <= m; i++) {
        scanf("%d", &x);
        addedge(n + i, t, x);
    }
    sum -= dinic(s, t);
    int tmp = 0;
    for (int i = n; !tmp; i--) tmp = i * !!level[i];
    for (int i = 1; i <= tmp; i++) {
        if (level[i]) printf("%d%c", i, " \n"[i == tmp]);
    }
    tmp = 0;
    for (int i = m; !tmp; i--) tmp = i * !!level[n + i];
    for (int i = 1; i <= tmp; i++) {
        if (level[n + i]) printf("%d%c", i, " \n"[i == tmp]);
    }
    printf("%d", sum);
}

试题库

题意

传送门：洛谷 P2763 - 试题库问题、LOJ 6006 - 试题库。

有 \(n\) 道题，\(k\) 种类型。每道题的类型是集合 \(T_i\)。你要从中选出 \(a_i\) 道 \(i\) 类型的题，每道题只能选一次。求一种可行的选择方案。

解法

考虑用流量限制每道题的选择次数。并对每道题和每个类型构点。

首先从 \(S\) 到 \(\text{题目}_i\) 连一条流量为 \(1\) 的边，即每道题只能选一次；

然后从 \(\text{类型}_i\) 到 \(T\) 连一条流量为 \(a_i\) 的边，即每种类型需要选 \(a_i\) 道；

最后 \(\forall j \in T_i\)，从 \(\text{题目}_i\) 给 \(\text{类型}_j\) 连边，即每道题可以以相应类型的名义被选出。

方案即是所有 题目到类型 的连边中满流的那些。如果流量不满则无解。

代码

这次毒瘤 LOJ 数据存在 \(\mathbf{a_i = 0}\) 的情况。

代码

#include <cstdio>
#include <cstring>
#include <queue>

const int N = 1e3 + 31, M = 3e4 + 43, K = 22, INF = 0x3f3f3f3f;

struct edge {
    int to, next, w;
} e[M << 1];
int head[N], cnt = 1;
void addedge(int x, int y, int z) {
    e[++cnt] = (edge){y, head[x], z};
    head[x] = cnt;
    e[++cnt] = (edge){x, head[y], 0};
    head[y] = cnt;
}

int level[N];
bool bfs(int s, int t) {
    memset(level, 0, sizeof level);
    std::queue<int> q;
    q.push(s);
    level[s] = 1;
    while (!q.empty()) {
        int pos = q.front();
        q.pop();
        for (int i = head[pos]; i; i = e[i].next) {
            int nx = e[i].to;
            if (level[nx] || !e[i].w) continue;
            level[nx] = level[pos] + 1;
            q.push(nx);
        }
    }
    return level[t];
}

int dfs(int s, int t, int flow) {
    if (s == t) return flow;
    int ret = 0;
    for (int i = head[s]; flow && i; i = e[i].next) {
        int nx = e[i].to;
        if (level[s] + 1 == level[nx] && e[i].w) {
            int tmp = dfs(nx, t, std::min(flow, e[i].w));
            e[i].w -= tmp;
            e[i ^ 1].w += tmp;
            ret += tmp;
            flow -= tmp;
        }
    }
    return ret;
}

int dinic(int s, int t) {
    int ret = 0;
    while (bfs(s, t)) ret += dfs(s, t, INF);
    return ret;
}

std::queue<int> out[K];
int n, k, x, y, sum;
int main() {
    scanf("%d%d", &k, &n);
    for (int i = 1; i <= k; i++) {
        scanf("%d", &x);
        addedge(n + i + 1, n + k + 2, x);
        sum += x;
    }
    for (int i = 1; i <= n; i++) {
        addedge(1, i + 1, 1);
        for (scanf("%d", &x); x--;) {
            scanf("%d", &y);
            addedge(i + 1, n + y + 1, 1);
        }
    }
    if (dinic(1, n + k + 2) != sum) return puts("No Solution!"), 0;
    for (int i = 1; i <= n; i++) {
        for (int j = head[i + 1]; j; j = e[j].next) {
            if ((~j & 1) && !e[j].w) {
                out[e[j].to - n - 1].push(i);
                break;
            }
        }
    }
    for (int i = 1; i <= k; i++) {
        printf("%d: ", i);
        if (out[i].empty()) puts("");
        while (!out[i].empty()) {
            printf("%d%c", out[i].front(), " \n"[out[i].size() == 1]);
            out[i].pop();
        }
    }
}

最小路径覆盖

题意

传送门：洛谷 P2764 - 最小路径覆盖问题、LOJ 6002 - 最小路径覆盖。

给一张 DAG，求最少用几条不相交简单路径可以覆盖整张图的所有点。并求出方案。

解法

如果没有最小的限制，那么直接输出 \(n\) 就好了 2333（逃

WA Output:
1 2 ... n
n

注意到这 \(n\) 条路径是可以合并的。

如果一条路径的终点和另一条路径的起点有连边，那么这两条路径是可以合并的。

但是一个终点或起点只能使用一次。比如三条路径 \(1 \to 3, 2 \to 3, 3 \to 4\)，你只能合并两条。

那么这道题就转化为了：最大化一个边集，使得边集中每个起点和终点都只使用过一次。即 最大独立边集。

这个显然是可以最大瘤流求的。把拆成入点 \(x\) 和出点 \(x’\)。从原点到 \(x'\) 连一条容量为 \(1\) 的边，从 \(x\) 到汇点连一条容量为 \(1\) 的边。边权用来限制每个起点或终点的使用次数。

对于每条边 \(x \to y\)，连接 \(x' \xrightarrow1 y\)。

因为每一条这样的边都意味着一次合并，所以答案是 \(n - \text{最大流}\)。

代码

LOJ 终于不毒瘤了！热泪盈眶

代码

#include <cstdio>
#include <cstring>
#include <queue>

const int N = 4e2 + 24, M = 6e3 + 36, INF = 0x3f3f3f3f;

struct edge {
    int to, next, w;
} e[M << 2];
int head[N], cnt = 1;
void addedge(int x, int y, int z) {
    e[++cnt] = (edge){y, head[x], z};
    head[x] = cnt;
    e[++cnt] = (edge){x, head[y], 0};
    head[y] = cnt;
}

int level[N];
bool bfs(int s, int t) {
    memset(level, 0, sizeof level);
    std::queue<int> q;
    q.push(s);
    level[s] = 1;
    while (!q.empty()) {
        int pos = q.front();
        q.pop();
        for (int i = head[pos]; i; i = e[i].next) {
            int nx = e[i].to;
            if (level[nx] || !e[i].w) continue;
            level[nx] = level[pos] + 1;
            q.push(nx);
        }
    }
    return level[t];
}

int dfs(int s, int t, int flow) {
    if (s == t) return flow;
    int ret = 0;
    for (int i = head[s]; flow && i; i = e[i].next) {
        int nx = e[i].to;
        if (level[nx] == level[s] + 1 && e[i].w) {
            int tmp = dfs(nx, t, std::min(flow, e[i].w));
            e[i].w -= tmp;
            e[i ^ 1].w += tmp;
            ret += tmp;
            flow -= tmp;
        }
    }
    if (!ret) level[s] = 0;
    return ret;
}

int dinic(int s, int t) {
    int ret = 0;
    while (bfs(s, t)) ret += dfs(s, t, INF);
    return ret;
}

bool vis[N];
void dfs(int x) {
    if (vis[x]) return;
    printf("%d ", x >> 1);
    vis[x] = 1;
    for (int i = head[x]; i; i = e[i].next) {
        if (!e[i].w && (~i & 1)) return dfs(e[i].to - 1);
    }
}

int n, m, x, y;
int main() {
    for (scanf("%d%d", &n, &m); m--;) {
        scanf("%d%d", &x, &y);
        addedge(2 * x, 2 * y + 1, 1);
    }
    for (int i = 1; i <= n; i++) {
        addedge(1, 2 * i, 1);
        addedge(2 * i + 1, 2 * n + 2, 1);
    }
    x = dinic(1, 2 * n + 2);
    vis[2 * n + 2] = 1;
    for (int i = 1; i <= n; i++) {
        if (!vis[2 * i]) {
            dfs(2 * i);
            puts("");
        }
    }
    printf("%d", n - x);
}

魔术球

题意

传送门：洛谷 P2765 - 魔术球问题、LOJ 6003 - 魔术球。

有 \(n\) 根柱子。你要往柱子上放编号为 \(1, 2, 3, \cdots\) 的球。满足同一根柱子上相邻两个球的编号之和为完全平方数。

\(n \le 55\)。

解法

考虑贪心。从 \(1\) 开始枚举球的编号。如果现成的柱子可以放这个球，那么直接放上去。否则就开个新柱子。

因为每一根柱子能否插入一个球，只和柱子顶端的球有关。所以放着能插入的柱子不管，而是另开一根柱子一定不会使答案变优。

这真的是网络流 24 题么？

代码

震惊！这货仍然全 OJ 通用！（逃

代码

#include <cmath>
#include <cstdio>
#include <vector>

const int M = 1e2 + 21;

std::vector<int> v[M];
int n, m, ans;

inline bool chk(int x) { return ((int)sqrt(x) * (int)sqrt(x)) == x; }
int main() {
    scanf("%d", &n);
    for (int i = 1; "QwQ"; i++) {
        for (int j = 1; j <= m; j++) {
            if (chk(i + v[j].back())) {
                v[j].push_back(i);
                goto end;
            }
        }
        if (n == m) {
            printf("%d\n", i - 1);
            break;
        }
        v[++m].push_back(i);
    end:;
    }
    for (int i = 1; i <= n; i++) {
        for (int j : v[i]) {
            printf("%d ", j);
        }
        puts("");
    }
}

最长递增子序列

题意

传送门：洛谷 P2766 - 最长不下降子序列问题、LOJ 6005 - 最长递增子序列。

给一个序列 \(a_{1 \cdots n}\)，求：

• 最长不下降子序列长度
• 最多可以取出多少个最长不下降子序列
• 允许无限次使用 \(a_1, a_n\)，最多可以取出多少个最长不下降子序列

注意：规则 3 中「无限次使用」必须满足 取出的每个序列下标不重复。

解法

第一问显然可以暴力 DP。令 \(len\) 为最长不下降子序列的长度。

第二问考虑最大流。我们希望每条从 \(S\) 到 \(T\) 的路径都代表一条 长度正好为 \(\mathbf{len}\) 的路径。

令 \(dp_i\) 为以 \(i\) 为结尾的最长不下降子序列长度。

那么我们可以按照 DP 值的转移路线连边。即 \(\forall dp_j + 1 = dp_i, j \xrightarrow1 i\)。

然后我们考虑从 \(S\) 连向 \(dp_i = 1\) 的所有点，从所有 \(dp_i = len\) 的点连向 \(T\)。

但是每个元素只能用一次。按照套路，我们把每个点拆成入点和出点，在入点和出点之间连一条容量为 \(1\) 的边。

最后求个最大流就好了。

第三问我们只要解除 \(a_1\) 和 \(a_n\) 的次数限制就好了。

即连接 \(S \xrightarrow{+\infty} 1 \xrightarrow{+\infty} 1'\)。如果 \(dp_n = len\)，连接 \(n \xrightarrow{+\infty} n' \xrightarrow{+\infty} T\)。

然后我在 LOJ 上就被叉掉了。

交 LOJ 记得特判 \(\mathbf{n = 1}\)！

再求一次最大流就好了。

代码

代码

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>

const int N = 1e3 + 31, M = 2e5 + 52, INF = 0x3f3f3f3f;
struct edge {
    int to, next, w;
} e[M << 1];
int head[N], cnt = 1;
void addedge(int x, int y, int z) {
    e[++cnt] = (edge){y, head[x], z}, head[x] = cnt;
    e[++cnt] = (edge){x, head[y], 0}, head[y] = cnt;
}

int lv[N];
bool bfs(int s, int t) {
    memset(lv, 0, sizeof lv);
    std::queue<int> q;
    q.push(s);
    lv[s] = 1;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = head[x]; i; i = e[i].next) {
            int nx = e[i].to;
            if (lv[nx] || !e[i].w) continue;
            lv[nx] = lv[x] + 1;
            q.push(nx);
        }
    }
    return lv[t];
}
int dfs(int s, int t, int f) {
    if (s == t) return f;
    int r = 0;
    for (int i = head[s]; f && i; i = e[i].next) {
        int nx = e[i].to;
        if (lv[nx] != lv[s] + 1 || !e[i].w) continue;
        int tmp = dfs(nx, t, std::min(f, e[i].w));
        f -= tmp;
        r += tmp;
        e[i].w -= tmp;
        e[i ^ 1].w += tmp;
    }
    return r;
}
int dinic(int s, int t) {
    int ret = 0;
    while (bfs(s, t)) ret += dfs(s, t, INF);
    return ret;
}

#define X(x) ((x) + 2)
#define Y(x) ((x) + n + 2)

int n, len, ans, a[N], dp[N];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
    }
    for (int i = 1; i <= n; len = std::max(len, dp[i++])) {
        for (int j = 0; j < i; j++) {
            if (a[j] <= a[i]) dp[i] = std::max(dp[i], dp[j] + 1);
        }
    }
    printf("%d\n", len);
    for (int i = 1; i <= n; i++) {
        addedge(X(i), Y(i), 1);
        if (dp[i] == 1) addedge(1, X(i), 1);
        if (dp[i] == len) addedge(Y(i), 2, 1);
        for (int j = 1; j < i; j++)
            if (a[j] <= a[i] && dp[j] + 1 == dp[i]) addedge(Y(j), X(i), 1);
    }
    printf("%d\n", ans = dinic(1, 2));
    addedge(1, X(1), INF), addedge(X(1), Y(1), INF);
    if (dp[n] == len && n != 1) addedge(Y(n), 2, INF), addedge(X(n), Y(n), INF);
    printf("%d", ans + dinic(1, 2));
}

航空路线问题

题意

传送门：洛谷 P2770 - 航空路线问题、LOJ 6122 - 航空路线问题。

求两条途径点数尽可能多的从 \(1\) 到 \(n\) 的不相交路线（\(1, n\) 除外）

解法

看到不相交，考虑拆点。

按照套路，每个点拆成入点和出点 \(x, x'\)。然后从 \(x\) 往 \(x'\) 连一条容量为 \(1\)，费用为 \(0\) 的边。

输入中每一条 \(x \to y\) 的边在网络流中就直接将 \(x'\) 向 \(y\) 连一条容量为 \(1\) 的边。

因为希望经过的点数尽量多，所以将费用设为 \(-1\) 跑最小费用最大流即可。

输出直接沿着满流边 dfs 两次就好了。注意输出顺序。

然后这题有一个坑点：必须特判 \(1 \leftrightarrow n\) 的边。

代码

又是一份两个 OJ 都能过的代码~

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <string>

const int N = 4e2 + 24, M = 2e3 + 32, INF = 0x3f3f3f3f;

struct edge {
    int to, next, w, c;
} e[M << 1];
int head[N], cnt = 1;
void addedge(int x, int y, int z, int w) {
    e[++cnt] = (edge){y, head[x], z, w}, head[x] = cnt;
    e[++cnt] = (edge){x, head[y], 0, -w}, head[y] = cnt;
}

void ek(int s, int t, int &mflow, int &mcost) {
    static int dis[N], vis[N], flow[N], pre[N];
    std::queue<int> q;
    mflow = mcost = 0;
    while (1) {
        memset(dis, 0x3f, sizeof dis);
        q.push(s);
        flow[s] = 0x3f3f3f3f;
        dis[s] = 0;
        while (!q.empty()) {
            int pos = q.front();
            vis[pos] = 0;
            q.pop();
            for (int i = head[pos]; i; i = e[i].next) {
                int nx = e[i].to;
                if (e[i].w && dis[nx] > dis[pos] + e[i].c) {
                    dis[nx] = dis[pos] + e[i].c;
                    flow[nx] = std::min(flow[pos], e[i].w);
                    pre[nx] = i;
                    if (!vis[nx]) {
                        q.push(nx);
                        vis[nx] = 1;
                    }
                }
            }
        }
        if (dis[t] == 0x3f3f3f3f) return;
        for (int i = pre[t]; i; i = pre[e[i ^ 1].to]) {
            e[i].w -= flow[t];
            e[i ^ 1].w += flow[t];
        }
        mflow += flow[t];
        mcost += dis[t] * flow[t];
    }
}

std::vector<std::string> vec;
std::string x$, y$, r[N];
int n;
void dfs1(int x) {
    if (x <= n) vec.push_back(r[x]);
    for (int i = head[x]; i; i = e[i].next) {
        if (!e[i].w && (~i & 1)) {
            dfs1(e[i].to);
            e[i].w = 1;
            break;
        }
    }
}
void dfs2(int x) {
    for (int i = head[x]; i; i = e[i].next) {
        if (!e[i].w && (~i & 1)) {
            dfs2(e[i].to);
            e[i].w = 1;
            break;
        }
    }
    if (x < n) vec.push_back(r[x]);
}

std::map<std::string, int> mp;
int m, x, y, f;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        std::cin >> r[i];
        mp[r[i]] = mp.size() + 1;
        addedge(i, i + n, 1, 0);
    }
    while (m--) {
        std::cin >> x$ >> y$;
        x = mp[x$], y = mp[y$];
        if (x > y) std::swap(x, y);
        f |= x == 1 && y == n;
        addedge(n + x, y, 1, -1);
    }
    addedge(1, n + 1, 1, 0);
    addedge(n, 2 * n, 1, 0);
    ek(1, 2 * n, x, y);
    if (!x || (x == 1 && !f)) return puts("No Solution!"), 0;
    if (x == 1 && f)
        return !printf("2\n%s\n%s\n%s", r[1].c_str(), r[n].c_str(),
                       r[1].c_str());
    dfs1(1);
    dfs2(1);
    printf("%lu\n", vec.size() - 1);
    for (const std::string &i : vec) {
        puts(i.c_str());
    }
}

方格取数

题意

传送门：洛谷 P2774 - 方格取数问题、LOJ 6007 - 方格取数。

给你一个 \(n\times m\) 的棋盘，每个格子上有一个数。你要在取的格子包含公共边的前提下使数的总和最大。

解法

首先对棋盘黑白染色，建二分图，在相邻的格子之间连边。

注意到我们要求的其实是 二分图的最大权独立集。

又有 （二分图）最大独立集 = 点权和 - 最大权匹配，所以我们只需要求出最大匹配就好了。

代码

代码

#include <cstdio>
#include <cstring>
#include <queue>

const int N = 2e4 + 42, M = 1e2 + 21,
          dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}, INF = 0x3f3f3f3f;

struct edge {
    int to, next, w;
} e[N << 4];
int head[N], cnt = 1;
void addedge(int x, int y, int z) {
    e[++cnt] = (edge){y, head[x], z};
    head[x] = cnt;
    e[++cnt] = (edge){x, head[y], 0};
    head[y] = cnt;
}

int level[N];
bool bfs(int s, int t) {
    memset(level, 0, sizeof level);
    std::queue<int> q;
    q.push(s);
    level[s] = 1;
    while (!q.empty()) {
        int pos = q.front();
        q.pop();
        for (int i = head[pos]; i; i = e[i].next) {
            int nx = e[i].to;
            if (level[nx] || !e[i].w) continue;
            level[nx] = level[pos] + 1;
            q.push(nx);
        }
    }
    return level[t];
}

int dfs(int s, int t, int flow) {
    if (s == t) return flow;
    int ret = 0;
    for (int i = head[s]; flow && i; i = e[i].next) {
        int nx = e[i].to;
        if (level[s] + 1 == level[nx] && e[i].w) {
            int tmp = dfs(nx, t, std::min(flow, e[i].w));
            e[i].w -= tmp;
            e[i ^ 1].w += tmp;
            ret += tmp;
            flow -= tmp;
        }
    }
    if (!ret) level[s] = 0;
    return ret;
}

int dinic(int s, int t) {
    int ret = 0;
    while (bfs(s, t)) ret += dfs(s, t, INF);
    return ret;
}

int n, m, a[M][M];
int id(int x, int y) { return (x - 1) * m + y + 2; }

long long sum;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", a[i] + j);
            sum += a[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if ((i + j) & 1)
                addedge(1, id(i, j), a[i][j]);
            else
                addedge(id(i, j), 2, a[i][j]);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if ((i + j) & 1) {
                for (int k = 0; k < 4; k++) {
                    int nx = i + dir[k][0], ny = j + dir[k][1];
                    if (nx < 1 || ny < 1 || nx > n || ny > m) continue;
                    addedge(id(i, j), id(nx, ny), INF);
                }
            }
        }
    }
    printf("%lld", sum - dinic(1, 2));
}

机器人路径规划

论文题，咕咕咕。

圆桌聚餐

题意

传送门：洛谷 P3254 - 圆桌问题、LOJ 6004 - 圆桌聚餐。

\(n\) 张餐桌，\(m\) 个单位。第 \(i\) 个餐桌容量为 \(c_i\)，第 \(i\) 个单位人数为 \(r_i\)。每个餐桌不允许出现两个同一单位的人。求一个可行的方案，或输出 \(0\)。

解法

考虑对桌子和单位构点。从源点连容量为 \(r_i\) 的边到单位 \(i\)，从餐桌 \(i\) 连容量为 \(c_i\) 的边到汇点。

注意到每个单位只能在每张桌子上放一个人。考虑从每个单位向每张桌子连一条容量为 \(1\) 的边。

如果最大流小于人数和则无解。

否则对于每个单位，枚举它的出边，输出满流边的终点即可。

代码

代码

#include <cstdio>
#include <cstring>
#include <queue>

const int N = 5e2 + 25, M = 6e4 + 46, INF = 0x3f3f3f3f;

struct edge {
    int to, next, w;
} e[M << 1];
int head[N], cnt = 1;
void addedge(int x, int y, int z) {
    e[++cnt] = (edge){y, head[x], z};
    head[x] = cnt;
    e[++cnt] = (edge){x, head[y], 0};
    head[y] = cnt;
}

int level[N];
bool bfs(int s, int t) {
    memset(level, 0, sizeof level);
    std::queue<int> q;
    level[s] = 1;
    q.push(s);
    while (!q.empty()) {
        int pos = q.front();
        q.pop();
        for (int i = head[pos]; i; i = e[i].next) {
            int nx = e[i].to;
            if (!e[i].w || level[nx]) continue;
            level[nx] = level[pos] + 1;
            q.push(nx);
        }
    }
    return level[t];
}

int dfs(int s, int t, int flow) {
    if (s == t) return flow;
    int ret = 0;
    for (int i = head[s]; flow && i; i = e[i].next) {
        int nx = e[i].to;
        if (level[nx] == level[s] + 1 && e[i].w) {
            int tmp = dfs(nx, t, std::min(flow, e[i].w));
            e[i].w -= tmp;
            e[i ^ 1].w += tmp;
            flow -= tmp;
            ret += tmp;
        }
    }
    if (!ret) level[s] = 0;
    return ret;
}

int dinic(int s, int t) {
    int ret = 0;
    while (bfs(s, t)) ret += dfs(s, t, INF);
    return ret;
}

std::vector<int> vec[N];
int n, m, x, s;

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &x);
        addedge(1, i + 2, x);
        s += x;
    }
    for (int i = 1; i <= m; i++) {
        scanf("%d", &x);
        addedge(n + i + 2, 2, x);
        for (int j = 1; j <= n; j++) {
            addedge(j + 2, n + i + 2, 1);
        }
    }
    if (dinic(1, 2) != s)
        return puts("0"), 0;
    else
        puts("1");
    for (int i = 2; i <= cnt; i += 2) {
        if (n + 2 < e[i].to && !e[i].w) {
            vec[e[i ^ 1].to - 2].push_back(e[i].to - n - 2);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j : vec[i]) {
            printf("%d ", j);
        }
        puts("");
    }
}

骑士共存问题

题意

传送门：洛谷 P3355 - 骑士共存问题、LOJ 6226 - 骑士共存问题。

求带障碍的 \(n \times n\) 的国际象棋棋盘可以放多少个马，使得两两之间互相不能攻击。

解法

首先每个马只能攻击与自己颜色不同的格子。考虑二分图。

还是老套路，将可以互相攻击的格子之间连一条边，然后求 二分图的最大独立集 即可。

因为 （二分图）最大独立集 = 点数 - 最大匹配，所以我们只需要求出最大匹配就好了。

代码

代码

#include <cstdio>
#include <cstring>
#include <queue>

const int N = 4e4 + 44, M = 4e5 + 54, K = 2e2 + 22, INF = 0x3f3f3f3f,
          dir[8][2] = {{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2},
                       {1, -2},  {1, 2},  {2, -1},  {2, 1}};

struct edge {
    int to, next, w;
} e[M << 1];
int head[N], cnt = 1;
void addedge(int x, int y, int z) {
    e[++cnt] = (edge){y, head[x], z};
    head[x] = cnt;
    e[++cnt] = (edge){x, head[y], 0};
    head[y] = cnt;
}

int level[N];
bool bfs(int s, int t) {
    memset(level, 0, sizeof level);
    std::queue<int> q;
    level[s] = 1;
    q.push(s);
    while (!q.empty()) {
        int pos = q.front();
        q.pop();
        for (int i = head[pos]; i; i = e[i].next) {
            int nx = e[i].to;
            if (!e[i].w || level[nx]) continue;
            level[nx] = level[pos] + 1;
            q.push(nx);
        }
    }
    return level[t];
}

int dfs(int s, int t, int flow) {
    if (s == t) return flow;
    int ret = 0;
    for (int i = head[s]; flow && i; i = e[i].next) {
        int nx = e[i].to;
        if (level[nx] == level[s] + 1 && e[i].w) {
            int tmp = dfs(nx, t, std::min(flow, e[i].w));
            e[i].w -= tmp;
            e[i ^ 1].w += tmp;
            flow -= tmp;
            ret += tmp;
        }
    }
    if (!ret) level[s] = 0;
    return ret;
}

int dinic(int s, int t) {
    int ret = 0;
    while (bfs(s, t)) ret += dfs(s, t, INF);
    return ret;
}

int n;
int id(int x, int y) { return (x - 1) * n + y + 2; }

int m, x, y, _[K][K];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &x, &y);
        _[x][y] = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (_[i][j]) continue;
            if (~(i + j) & 1) {
                addedge(id(i, j), 2, 1);
                continue;
            }
            addedge(1, id(i, j), 1);
            for (int k = 0; k < 8; k++) {
                int nx = i + dir[k][0], ny = j + dir[k][1];
                if (nx < 1 || ny < 1 || nx > n || ny > n || _[nx][ny]) continue;
                addedge(id(i, j), id(nx, ny), 1);
            }
        }
    }
    printf("%d", n * n - m - dinic(1, 2));
}

火星探险问题

题意

传送门：洛谷 P3356 - 火星探险问题、LOJ 6225 - 火星探险问题。

有障碍、多路径的方格取数（LP1004）。

解法

注意到一个点只能取一次。根据套路我们拆成点 \(x, x'\)。

因为第一个踩到的机器人会采集，所以在 \(x\) 和 \(x'\) 之间连一条容量为 \(1\)，费用为 \(-1\) 的边。

因为接下来踩到的什么事都没有，所以在 \(x\) 和 \(x'\) 之间连一条容量为 \(+\infty\)，费用为 \(0\) 的边。

然后从 \(S\) 向 \((1, 1)\)，从 \((n, m)'\) 到 \(T\) 连一条容量为 \(k\)、费用为 \(0\) 的边。

然后跑费用流就好了。输出方案用 DFS。

注意：在输出方案的时候，不要经过入点，否则会重复输出。

代码

代码

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>

const int N = 4e3 + 34, M = 1e5 + 51, INF = 0x3f3f3f3f;
struct edge {
    int to, next, w, c;
} e[M << 1];
int head[N], cnt = 1;
inline void addedge(int x, int y, int z, int w) {
    e[++cnt] = (edge){y, head[x], z, w}, head[x] = cnt;
    e[++cnt] = (edge){x, head[y], 0, -w}, head[y] = cnt;
}
inline void ek(int s, int t, int& n, int& m) {
    static int dis[N], vis[N], flow[N], pre[N];
    std::queue<int> q;
    n = m = 0;
    while (">_<") {
        memset(dis, 0x3f, sizeof dis);
        flow[s] = INF;
        dis[s] = 0;
        q.push(s);
        while (!q.empty()) {
            int x = q.front();
            vis[x] = 0;
            q.pop();
            for (int i = head[x]; i; i = e[i].next) {
                int nx = e[i].to;
                if (e[i].w && dis[nx] > dis[x] + e[i].c) {
                    dis[nx] = dis[x] + e[i].c;
                    flow[nx] = std::min(flow[x], e[i].w);
                    pre[nx] = i;
                    if (!vis[nx]) vis[nx] = 1, q.push(nx);
                }
            }
        }
        if (dis[t] == 0x3f3f3f3f) return;
        for (int i = pre[t]; i; i = pre[e[i ^ 1].to]) {
            e[i].w -= flow[t];
            e[i ^ 1].w += flow[t];
        }
        n += flow[t];
        m += flow[t] * dis[t];
    }
}

int n, m, k;
inline int id(int x, int y, int z) { return ((x - 1) * m + y + 1) * 2 + z; }

void dfs(int p, int x) {
    if (x == id(n, m, 1)) return;
    for (int i = head[x]; i; i = e[i].next) {
        if (e[i ^ 1].w && x < e[i].to) {
            e[i ^ 1].w--;
            printf("%d %d\n", p, e[i].to - x == 1);
            return dfs(p, e[i].to + 1);
        }
    }
}

int x, y;
int main() {
    scanf("%d%d%d", &k, &m, &n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &x);
            if (x & 1) continue;
            addedge(id(i, j, 0), id(i, j, 1), INF, 0);
            if (x) addedge(id(i, j, 0), id(i, j, 1), 1, -1);
            if (1 < i) addedge(id(i - 1, j, 1), id(i, j, 0), INF, 0);
            if (1 < j) addedge(id(i, j - 1, 1), id(i, j, 0), INF, 0);
        }
    }
    addedge(1, id(1, 1, 0), k, 0);
    addedge(id(n, m, 1), 2, k, 0);
    ek(1, 2, x, y);
    // return !printf("%d", -y);
    for (int i = 1; i <= k; i++) dfs(i, id(1, 1, 1));
}

最长 k 可重线段集问题

博客传送门：这里。

最长 k 可重区间集问题

题意

传送门：洛谷 P3358 - 最长k可重区间集问题、LOJ 6014 - 最长 k 可重区间集。

给一个开区间集合 \(I\)，问如何选一个集合 \(S \subseteq I\)，使得 \(\forall i, \sum_{j \in S}[i \in j] \le k\)，且 \(\sum_{i \in S}|i|\) 最大。求最大值。

解法

首先离散化区间端点，将值域缩小到 \([1, 2n]\)。然后 \(S \xrightarrow{k, 0} 1, i \xrightarrow{k, 0} (i+1), 2n \xrightarrow{k, 0} T\)。

对于每条线段，我们从左端点向右端点连一条流量为 \(1\) 的边。这会使开区间 \((l, r)\) 的可支配流量 \(-1\)，代表能选的互相覆盖的区间数减了 \(1\)。

因为我们希望选的边长度和尽量大，这条边的费用为 \(\mathbf{l - r}\)。

跑一个最小费用最大流后，费用的相反数即为答案。

代码

LOJ 数据竟然有 \(\mathbf{r > l}\) 的情况……反人类

代码

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>

const int N = 2e3 + 32, M = 2e6 + 62, INF = 0x3f3f3f3f;

struct edge {
    int to, next, w, c;
} e[M << 1];
int head[N], cnt = 1;
void addedge(int x, int y, int z, int w) {
    e[++cnt] = (edge){y, head[x], z, w};
    head[x] = cnt;
    e[++cnt] = (edge){x, head[y], 0, -w};
    head[y] = cnt;
}

void ek(int s, int t, int &mflow, int &mcost) {
    static int dis[N], vis[N], flow[N], pre[N];
    std::queue<int> q;
    mflow = mcost = 0;
    while (1) {
        memset(dis, 0x3f, sizeof dis);
        q.push(s);
        flow[s] = 0x3f3f3f3f;
        dis[s] = 0;
        while (!q.empty()) {
            int pos = q.front();
            vis[pos] = 0;
            q.pop();
            for (int i = head[pos]; i; i = e[i].next) {
                int nx = e[i].to;
                if (e[i].w && dis[nx] > dis[pos] + e[i].c) {
                    dis[nx] = dis[pos] + e[i].c;
                    flow[nx] = std::min(flow[pos], e[i].w);
                    pre[nx] = i;
                    if (!vis[nx]) {
                        q.push(nx);
                        vis[nx] = 1;
                    }
                }
            }
        }
        if (dis[t] == 0x3f3f3f3f) return;
        for (int i = pre[t]; i; i = pre[e[i ^ 1].to]) {
            e[i].w -= flow[t];
            e[i ^ 1].w += flow[t];
        }
        mflow += flow[t];
        mcost += dis[t] * flow[t];
    }
}

int n, k, x, y, l[N], r[N];
int t[N], _;

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", l + i, r + i);
        t[++_] = l[i], t[++_] = r[i];
        if (l[i] > r[i]) std::swap(l[i], r[i]);
    }
    std::sort(t + 1, t + _ + 1);
    addedge(1, 2, k, 0);
    for (int i = 1; i <= _; i++) {
        addedge(i + 1, i + 2, INF, 0);
    }
    for (int i = 1; i <= n; i++) {
        l[i] = std::lower_bound(t + 1, t + _ + 1, l[i]) - t;
        r[i] = std::lower_bound(t + 1, t + _ + 1, r[i]) - t;
        addedge(l[i] + 1, r[i] + 1, 1, t[l[i]] - t[r[i]]);  // 相反数
    }
    ek(1, _ + 2, x, y);
    printf("%d", -y);
}

汽车加油行驶问题

题意

传送门：洛谷 P4009 - 汽车加油行驶问题、LOJ 6223 - 汽车加油行驶问题。

给一个 \(n \times n\) 的地图。你要从 \((1, 1)\) 到 \((n, n)\)。

• 你的油箱最开始是满的，每走一格耗一格油，总共有 \(k\) 格油。
• 你可以往→和↓两个方向走。如果你逆行就要罚款 \(B\) 块。
• 有一些点有加油站，踩到加油站就要被强制消费 \(A\) 块并加满油。
• 如果你想在没加油站的地方加油，你可以付 \(A+C\) 块。这样你的车就会被膜法加满油。

问你最少要被坑多少钱。\(n \le 100, k \le 10\)。

解法

我偏不用网络流

考虑分层图最短路。\((lv, x, y)\) 代表你在 \((x, y)\) 处，油箱里有 \(lv\) 格油。

那么对于加油站，有 \((lv, x, y) \xrightarrow A (k, x, y)\)。

对于非加油站的点，有下面几种边：

• 空中加油：\((lv, x, y) \xrightarrow{A+B} (k, x, y)\)。
• 顺行：\((lv, x, y) \xrightarrow0 (lv-1, x + 1, y), (lv-1, x, y + 1)\)。
• 逆行：\((lv, x, y) \xrightarrow B (lv-1, x + 1, y), (lv-1, x, y + 1)\)。

然后跑一个 SPFA 就好了死不掉的。

代码

代码

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>

const int N = 1e2 + 21, K = 22, dir[4][2] = {{1, 0}, {0, 1}, {0, -1}, {-1, 0}};

struct node {
    int lv, x, y;
};

int dis[K][N][N], vis[K][N][N], _[N][N];
int n, k, a, b, c, ans = 0x3f3f3f3f;
std::queue<node> q;
int main() {
    scanf("%d%d%d%d%d", &n, &k, &a, &b, &c);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", _[i] + j);
        }
    }
    memset(dis, 0x3f, sizeof dis);
    q.push((node){k, 1, 1});
    dis[k][1][1] = 0;
    while (!q.empty()) {
        int lv = q.front().lv, x = q.front().x, y = q.front().y;
        vis[lv][x][y] = 0;
        q.pop();
        if (_[x][y] && lv < k) {
            if (dis[k][x][y] > dis[lv][x][y] + a) {
                dis[k][x][y] = dis[lv][x][y] + a;
                if (!vis[k][x][y]) vis[k][x][y] = 1, q.push((node){k, x, y});
            }
        } else {
            if (dis[k][x][y] > dis[lv][x][y] + a + c) {
                dis[k][x][y] = dis[lv][x][y] + a + c;
                if (!vis[k][x][y]) vis[k][x][y] = 1, q.push((node){k, x, y});
            }
            if (lv)
                for (int i = 0; i < 4; i++) {
                    int nx = x + dir[i][0], ny = y + dir[i][1];
                    if (nx < 1 || ny < 1 || nx > n || ny > n) continue;
                    if (dis[lv - 1][nx][ny] > dis[lv][x][y] + (i > 1) * b) {
                        dis[lv - 1][nx][ny] = dis[lv][x][y] + (i > 1) * b;
                        if (!vis[lv - 1][nx][ny]) vis[lv - 1][nx][ny] = 1, q.push((node){lv - 1, nx, ny});
                    }
                }
        }
    }
    for (int i = 0; i <= k; i++) ans = std::min(ans, dis[i][n][n]);
    printf("%d", ans);
}

孤岛营救问题

题意

传送门：洛谷 P4011 - 孤岛营救问题、LOJ 6121 - 孤岛营救问题。

给你一个 \(n \times n\) 的魔塔地图。每把钥匙可以用无数次。问要多久可以从 \((1, 1)\) 走到 \((n, n)\)。魔塔玩家的福音

钥匙最多有 \(10\) 种。

解法

考虑分层图。\((lv, x, y)\) 代表你在 \((x, y)\) 处，手上的钥匙集合是 \(lv\)（状压）。

令 \(wall_{x, y, dir}\) 为 \((x, y)\) 的 \(dir\) 方向上的墙需要的钥匙种类，令 \(key_{x, y}\) 为 \((x, y)\) 上的钥匙集合。

为了方便，不可通过的墙可以将 \(wall_{x, y, dir}\) 设为 \(2^{11}\)。

因为所有类型门都已经归为钥匙门的子集，我们可以直接按下列方式连边：

\(\forall (lv, x, y, dir), \text{if}~wall_{x,y,dir} \subseteq lv, \text{then}~(lv, x, y) \xrightarrow1 (lv \operatorname{or} key_{nx, ny}, nx, ny)\)。其中 \(nx, ny\) 代表新的坐标。

因为所有边的边权都是 \(1\)，所以直接 BFS 即可。

代码

代码

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <tuple>

typedef std::tuple<int, int, int, int> t4;
const int N = 22, M = 1024, dir[4][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}, INF = 0x3f3f3f3f;

int n, m, p, k, a, b, c, d, e_, lv, x, y, ans = INF;
int key[N][N], wall[N][N][4], vis[M][N][N];
std::queue<t4> q;
int main() {
    for (scanf("%d%d%d%d", &n, &m, &p, &k); k--;) {
        scanf("%d%d%d%d%d", &a, &b, &c, &d, &e_);
        if (!e_--) e_ = 11;
        for (int i = 0; i < 4; i++) {
            if (c == a + dir[i][0] && d == b + dir[i][1]) {
                wall[a][b][i] = 1 << e_;
                wall[c][d][i ^ 1] = 1 << e_;
                continue;
            }
        }
    }
    for (scanf("%d", &k); k--; key[a][b] |= 1 << (c - 1)) scanf("%d%d%d", &a, &b, &c);
    q.emplace(0, 1, 1, key[1][1]);
    while (!q.empty()) {
        std::tie(lv, x, y, d) = q.front(), q.pop();
        if (x == n && y == m) return !printf("%d", d);
        for (int i = 0; i < 4; i++) {
            if ((wall[x][y][i] & lv) != wall[x][y][i]) continue;
            int nx = x + dir[i][0], ny = y + dir[i][1], nlv = lv | key[nx][ny];
            if (nx < 1 || ny < 1 || nx > n || ny > m) continue;
            if (!vis[nlv][nx][ny]) {
                vis[nlv][nx][ny] = 1;
                q.emplace(nlv, nx, ny, d + 1);
            }
        }
    }
    puts("-1");
}

深海机器人问题

题意

传送门：洛谷 P4012 - 深海机器人问题、LOJ 6224 - 深海机器人问题。

有一个 \((n+1) \times (m+1)\) 的棋盘，每条边上有一个数字。有 \(a\) 个起点和 \(b\) 个终点，每个起点有 \(k_i\) 个机器人，每个终点可以存 \(r_i\) 个机器人。机器人走一条边就会收集这条边的数字。问能收集到的数字的和的最大值是多少……

本蒟蒻脑子抽了，请自行查看原题

解法

根据 火星探险问题 的套路，我们在两两格子之间连两条边：一条边容量为 \(1\)，费用为权值的相反数，另一条容量无限，费用为 \(0\)。

然后对于每个起点，从源点连一条容量为 \(k_i\) 的边。终点同理。

代码

代码

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>

const int N = 1e3 + 31, M = 1e4 + 41, INF = 0x3f3f3f3f;
struct edge {
    int to, next, w, c;
} e[M << 1];
int head[N], cnt = 1;
inline void addedge(int x, int y, int z, int w) {
    e[++cnt] = (edge){y, head[x], z, w}, head[x] = cnt;
    e[++cnt] = (edge){x, head[y], 0, -w}, head[y] = cnt;
}
inline void ek(int s, int t, int& n, int& m) {
    static int vis[N], dis[N], flow[N], pre[N];
    std::queue<int> q;
    n = m = 0;
    while ("QwQ") {
        memset(dis, 0x3f, sizeof dis);
        flow[s] = INF;
        dis[s] = 0;
        q.push(s);
        while (!q.empty()) {
            int x = q.front();
            vis[x] = 0;
            q.pop();
            for (int i = head[x]; i; i = e[i].next) {
                int nx = e[i].to;
                if (e[i].w && dis[nx] > dis[x] + e[i].c) {
                    dis[nx] = dis[x] + e[i].c;
                    flow[nx] = std::min(flow[x], e[i].w);
                    pre[nx] = i;
                    if (!vis[nx]) vis[nx] = 1, q.push(nx);
                }
            }
        }
        if (dis[t] == INF) return;
        for (int i = pre[t]; i; i = pre[e[i ^ 1].to]) {
            e[i].w -= flow[t];
            e[i ^ 1].w += flow[t];
        }
        n += flow[t];
        m += flow[t] * dis[t];
    }
}

int n, m;
inline int id(int x, int y) { return x * 20 + y + 3; }

int a, b, x, y, z;
int main() {
    scanf("%d%d%d%d", &a, &b, &n, &m);
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &x);
            addedge(id(i, j), id(i, j + 1), 1, -x);
            addedge(id(i, j), id(i, j + 1), INF, 0);
        }
    }
    for (int j = 0; j <= m; j++) {
        for (int i = 0; i < n; i++) {
            scanf("%d", &x);
            addedge(id(i, j), id(i + 1, j), 1, -x);
            addedge(id(i, j), id(i + 1, j), INF, 0);
        }
    }
    for (; a--; addedge(1, id(y, z), x, 0)) scanf("%d%d%d", &x, &y, &z);
    for (; b--; addedge(id(y, z), 2, x, 0)) scanf("%d%d%d", &x, &y, &z);
    ek(1, 2, x, y);
    printf("%d", -y);
}

数字梯形问题

题意

传送门：洛谷 P4013 - 数字梯形问题、LOJ 6010 - 数字梯形。

给你一个 \(n\) 层的数字梯形，最顶层有 \(m\) 个数。你要求出 \(m\) 条从顶层各数出发的路径，满足下列三种规则：

1. 路径的点和边都不能相交
2. 路径的边不能相交
3. 随你相交

使得这些路径上数字的总和最大。

解法

网络流大模拟……其实没什么思维难度吧……

第一问

注意到如果点之间不相交，那么边之间一定不相交。

点之间不相交直接套路拆点即可。在 \(x\) 和 \(x'\) 之间连一条容量为 \(1\)，费用为权值的相反数的边。

两个点之间连一条容量为 \(1\)、费用为 \(0\) 的边。

跑费用流即可。

第二问

懒癌发作，不想重新构图。

注意到第二问其实是删除了点的限制。所以直接在 \(x\) 和 \(x'\) 之间连一条容量为 \(+\infty\) 的边。

……等等，还要在底层和 \(T\) 之间连一条容量为 \(+\infty\) 的边。不然路径终点仍然被限制了。

然后清空流量跑一遍费用流。

第三问

还是不想重新构图。

只需要把所有数字之间的边都扩容就好了。

然后再清空流量跑一遍费用流。

代码

代码

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>

const int N = 4e3 + 34, M = 2e5 + 52, K = 52, INF = 0x3f3f3f3f;

struct edge {
    int to, next, w, c;
} e[M << 1];
int head[N], cnt = 1;
void addedge(int x, int y, int z, int w) {
    e[++cnt] = (edge){y, head[x], z, w}, head[x] = cnt;
    e[++cnt] = (edge){x, head[y], 0, -w}, head[y] = cnt;
}

void ek(int s, int t, int& n, int& m) {
    static int dis[N], vis[N], flow[N], pre[N];
    std::queue<int> q;
    n = m = 0;
    while (1) {
        memset(dis, 0x3f, sizeof dis);
        flow[s] = INF, dis[s] = 0;
        for (q.push(s); !q.empty();) {
            int x = q.front();
            vis[x] = 0;
            q.pop();
            for (int i = head[x]; i; i = e[i].next) {
                int nx = e[i].to;
                if (e[i].w && dis[nx] > dis[x] + e[i].c) {
                    dis[nx] = dis[x] + e[i].c;
                    flow[nx] = std::min(flow[x], e[i].w);
                    pre[nx] = i;
                    if (!vis[nx]) {
                        vis[nx] = 1;
                        q.push(nx);
                    }
                }
            }
        }
        if (dis[t] == INF) return;
        for (int i = pre[t]; i; i = pre[e[i ^ 1].to]) {
            e[i].w -= flow[t];
            e[i ^ 1].w += flow[t];
        }
        n += flow[t];
        m += flow[t] * dis[t];
    }
}

int m, n, x, y, a[K][K], id[K][K], _ = 1;
int main() {
    scanf("%d%d", &m, &n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < m + i; j++) {
            scanf("%d", a[i] + j);
            id[i][j] = _ += 2;
        }
    }
    for (int i = 1; i <= m; i++) addedge(1, id[1][i], 1, 0);
    for (int i = 1; i <= n + m; i++) addedge(id[n][i] + 1, 2, 1, 0);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < m + i; j++) {
            addedge(id[i][j], id[i][j] + 1, 1, -a[i][j]);
            if (i < n) {
                addedge(id[i][j] + 1, id[i + 1][j], 1, 0);
                addedge(id[i][j] + 1, id[i + 1][j + 1], 1, 0);
            }
        }
    }
    ek(1, 2, x, y);
    printf("%d\n", -y);

    for (int i = 2; i <= cnt; i += 2) e[i].w += e[i ^ 1].w, e[i ^ 1].w = 0;
    for (int i = 1; i <= n + m; i++) addedge(id[n][i] + 1, 2, 0x3f3f3f3f, 0);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < m + i; j++) {
            addedge(id[i][j], id[i][j] + 1, 0x3f3f3f3f, -a[i][j]);
        }
    }
    ek(1, 2, x, y);
    printf("%d\n", -y);

    for (int i = 2; i <= cnt; i += 2) e[i].w += e[i ^ 1].w, e[i ^ 1].w = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < m + i; j++) {
            if (i < n) {
                addedge(id[i][j] + 1, id[i + 1][j], INF, 0);
                addedge(id[i][j] + 1, id[i + 1][j + 1], INF, 0);
            }
        }
    }
    ek(1, 2, x, y);
    printf("%d", -y);
}

分配问题

题意

传送门：洛谷 P4014 - 分配问题、LOJ 6012 - 分配问题。

有 \(n\) 件工作要分配给 \(n\) 个人做。第 \(i\) 个人做第 \(j\) 件工作产生的效益为 \(c_{i,j}\)。试设计一个将 \(n\) 件工作分配给 \(n\) 个人做的分配方案，使产生的总效益最大。

解法

显然对人和工作构点。人和工作是一一对应的，所以源点向每个人、每个工作向汇点连一条容量 \(1\) 费用 \(0\) 的边。

然后第 \(i\) 个人向第 \(j\) 个工作连一条容量 \(1\) 费用 \(-c_{i,j}\) 的边。最后求一个最小费用最大流即可。

代码

代码

#include <cstdio>
#include <cstring>
#include <queue>

const int N = 2e2 + 22, M = 2e4 + 42;
struct edge {
    int to, next, w, c;
} e[M << 1];
int head[N], cnt = 1;
void addedge(int x, int y, int z, int w) {
    e[++cnt] = (edge){y, head[x], z, w};
    head[x] = cnt;
    e[++cnt] = (edge){x, head[y], 0, -w};
    head[y] = cnt;
}

void ek(int s, int t, int &mflow, int &mcost) {
    static int dis[N], vis[N], flow[N], pre[N];
    std::queue<int> q;
    mflow = mcost = 0;
    while (1) {
        memset(dis, 0x3f, sizeof dis);
        q.push(s);
        flow[s] = 0x3f3f3f3f;
        dis[s] = 0;
        while (!q.empty()) {
            int pos = q.front();
            vis[pos] = 0;
            q.pop();
            for (int i = head[pos]; i; i = e[i].next) {
                int nx = e[i].to;
                if (e[i].w && dis[nx] > dis[pos] + e[i].c) {
                    dis[nx] = dis[pos] + e[i].c;
                    flow[nx] = std::min(flow[pos], e[i].w);
                    pre[nx] = i;
                    if (!vis[nx]) {
                        q.push(nx);
                        vis[nx] = 1;
                    }
                }
            }
        }
        if (dis[t] == 0x3f3f3f3f) return;
        for (int i = pre[t]; i; i = pre[e[i ^ 1].to]) {
            e[i].w -= flow[t];
            e[i ^ 1].w += flow[t];
        }
        mflow += flow[t];
        mcost += dis[t] * flow[t];
    }
}

int n, x, y, c[N][N];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        addedge(1, i + 2, 1, 0);
        addedge(n + i + 2, 2, 1, 0);
        for (int j = 1; j <= n; j++) {
            scanf("%d", c[i] + j);
            addedge(i + 2, n + j + 2, 1, c[i][j]);
        }
    }
    ek(1, 2, x, y);
    printf("%d\n", y);
    memset(head, 0, sizeof head);
    cnt = 1;
    for (int i = 1; i <= n; i++) {
        addedge(1, i + 2, 1, 0);
        addedge(n + i + 2, 2, 1, 0);
        for (int j = 1; j <= n; j++) {
            addedge(i + 2, n + j + 2, 1, -c[i][j]);
        }
    }
    ek(1, 2, x, y);
    printf("%d", -y);
}

运输问题

题意

\(n\) 个仓库 \(m\) 个商店。\(i\) 仓库有 \(a_i\) 单位货物，\(i\) 商店需要 \(b_i\) 单位货物。\(i\) 仓库到 \(j\) 商店的运费是 \(c_{i,j} / \text{单位}\)。问最小运输费用和最大运输费用。

解法

对于第一问，只需要 \(S \xrightarrow{a_i, 0} \text{仓库}_i, \text{仓库}_i \xrightarrow{+\infty, c_{i,j}} \text{商店}_j, \text{商店}_i \xrightarrow{b_i, 0} T\) 然后跑最小费用最大流就好了。

第二问只要把仓库到商店的边费用取相反数再跑一遍就好了。

代码

代码

#include <cstdio>
#include <cstring>
#include <queue>

const int N = 2e2 + 22, INF = 0x3f3f3f3f;

struct edge {
    int to, next, w, c;
} e[N * N * 4];
int head[N], cnt;
void addedge(int x, int y, int z, int w) {
    e[++cnt] = (edge){y, head[x], z, w};
    head[x] = cnt;
    e[++cnt] = (edge){x, head[y], 0, -w};
    head[y] = cnt;
}

void ek(int s, int t, int &mflow, int &mcost) {
    static int dis[N], vis[N], flow[N], pre[N];
    std::queue<int> q;
    mflow = mcost = 0;
    while (1) {
        memset(dis, 0x3f, sizeof dis);
        q.push(s);
        flow[s] = 0x3f3f3f3f;
        dis[s] = 0;
        while (!q.empty()) {
            int pos = q.front();
            vis[pos] = 0;
            q.pop();
            for (int i = head[pos]; i; i = e[i].next) {
                int nx = e[i].to;
                if (e[i].w && dis[nx] > dis[pos] + e[i].c) {
                    dis[nx] = dis[pos] + e[i].c;
                    flow[nx] = std::min(flow[pos], e[i].w);
                    pre[nx] = i;
                    if (!vis[nx]) {
                        q.push(nx);
                        vis[nx] = 1;
                    }
                }
            }
        }
        if (dis[t] == 0x3f3f3f3f) return;
        for (int i = pre[t]; i; i = pre[e[i ^ 1].to]) {
            e[i].w -= flow[t];
            e[i ^ 1].w += flow[t];
        }
        mflow += flow[t];
        mcost += dis[t] * flow[t];
    }
}

int n, m, a[N], b[N], c[N][N];
void build(int off) {
    memset(head, 0, sizeof head);
    cnt = 1;
    for (int i = 1; i <= n; i++) {
        addedge(1, i + 1, a[i], 0);
        for (int j = 1; j <= m; j++) {
            addedge(i + 1, j + n + 1, INF, c[i][j] * off);
        }
    }
    for (int i = 1; i <= m; i++) {
        addedge(i + n + 1, n + m + 2, b[i], 0);
    }
}

int x, y;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
    }
    for (int i = 1; i <= m; i++) {
        scanf("%d", b + i);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", c[i] + j);
        }
    }
    build(1);
    ek(1, n + m + 2, x, y);
    printf("%d\n", y);
    build(-1);
    ek(1, n + m + 2, x, y);
    printf("%d", -y);
}