刷题记（网络流 V - 网络流24题 II）

网络流24题 II

BB

赶作业更新慢了点QAQ

Introduction

本次不包含24题中的三道题目，分别为：《机器人路径规划问题》（不知道咋做+没题解），《深海机器人问题》（与《火星探险》解法类似），《最长k可重线段集问题》（投影到x轴后与《最长k可重区间集问题》相同，需要特判垂直于x轴的情况）

网络流24题
https://www.cnblogs.com/Capella/p/8192729.html

最长不下降子序列问题 - luogu P2766

Description
Sample Input

4
3 6 2 5

Sample Output

2
2
3

Solution - 二分图最大匹配
第一问：裸的LIS
第二问：建图
S -> {i}, cap = 1: f[i] = 1
{j} -> {i}, cap = 1: i > j, f[i] = f[j] + 1, a[i] >= a[j]
{i} -> T, cap = 1: f[i] = lis
跑最大流即可
这里的f[i]是指以a[i]结尾的序列的lis为f[i]，要使能够取出长度为lis的序列，对于a[i]而言，其只能接在满足f[i] = f[j] + 1, a[i] >= a[j]的元素a[j]之后，否则会使得长度取不到lis
第三问：在第二问的基础上建图
S -> {1}, cap = inf
{n} -> T, cap = inf: f[n] = lis
显然，取消a[1]与a[n]限制即可

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < i; j++) {
            if(a[i] >= a[j]) {
                f[i] = max(f[i], f[j] + 1);
            }
        }
    }
    int lis = *max_element(f + 1, f + 1 + n);
    cout << lis << "\n";

    init();
    int ss = 0, tt = 2001;
    for(int i = 1; i <= n; i++) {
        if(f[i] == 1) {
            addEdge(ss, i, 1);
        }
        if(f[i] == lis) {
            addEdge(i + 1000, tt, 1);
        }
        addEdge(i, i + 1000, 1);
    }
    for(int i = 1; i <= n; i++) {
        for(int j = i + 1; j <= n; j++) {
            if(f[i] + 1 == f[j] && a[i] <= a[j]) {
                addEdge(i + 1000, j, 1);
            }
        }
    }
    int max_flow = ISAP(2 * n + 2, ss, tt);
    cout << max_flow << "\n";

    init();
    for(int i = 1; i <= n; i++) {
        if(f[i] == 1) {
            addEdge(ss, i, 1);
        }
        if(f[i] == lis) {
            addEdge(i + 1000, tt, 1);
        }
        addEdge(i, i + 1000, 1);
    }
    for(int i = 1; i <= n; i++) {
        for(int j = i + 1; j <= n; j++) {
            if(f[i] + 1 == f[j] && a[i] <= a[j]) {
                addEdge(i + 1000, j, 1);
            }
        }
    }
    addEdge(ss, 1, inf);
    addEdge(1, 1 + 1000, inf);
    if(f[n] == lis) {
        addEdge(n, n + 1000, inf);
        addEdge(n + 1000, tt, inf);
    }
    max_flow = ISAP(2 * n + 2, ss, tt);
    cout << max_flow << "\n";
}

试题库问题 - luogu P2763

Description
Sample Input

Sample Output

1 6 8
7 9 10
2 3 4 5

Solution
与《圆桌问题》相同，故不赘述

餐巾计划问题 - luogu P1251

Description
Sample Input

3
1 7 5
11 2 2 3 1

Sample Output

Solution
此题的确想不太到 QAQ
将点i拆为i与i'，建图
{i'} -> T, cap = ri, cost = 0，满流代表毛巾供应ok，因此需要考虑i'的流入问题
S -> {i'}, cap = inf, cost = p，代表买新毛巾
{i} -> {(i + m)'}, cap = inf, cost = f，代表快洗
{i} -> {(i + n)'}, cap = inf, cost = s，代表慢洗
{i} -> {i + 1}, cap = inf, cost = 0，代表屯旧毛巾
S -> {i}, cap = ri, cost = 0，代表每天产生的旧毛巾
跑MCMF即可

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    init();
    int n, a, d1, b, d2, c;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> r[i];
    }
    cin >> a >> d1 >> b >> d2 >> c;
    int ss = 0, tt = 2 * n + 1;
    for(int i = 1; i <= n; i++) {
        addEdge(ss, i, r[i], 0);
        addEdge(ss, i + n, inf, a);
        if(i + 1 <= n) {
            addEdge(i, i + 1, inf, 0);
        }
        if(i + d1 <= n) {
            addEdge(i, i + d1 + n, inf, b);
        }
        if(i + d2 <= n) {
            addEdge(i, i + d2 + n, inf, c);
        }
        addEdge(i + n, tt, r[i], 0);
    }
    pair<int, ll> ans = solve(ss, tt, tt + 1);
    cout << ans.second << "\n";
}

软件补丁问题 - luogu P2761

Description
Sample Input

3
000 00-
00- 0-+
0-- -++

Sample Output

Solution
显然是状压搜索
注意不要一次性构图，会MLE QAQ

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int N = (int)(1 << 20) + 15;
const int inf = 0x3f3f3f3f;

int b1[105], b2[105], f1[105], f2[105], weight[105];
int d[N];

void dijkstra(int src, int des, int m) {
    memset(d, 0x3f, sizeof(d));
    d[src] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > que;
    que.push(make_pair(0, src));
    while(!que.empty()) {
        pair<int, int> ele = que.top();
        que.pop();
        int u = ele.second, w = ele.first;

        if(w > d[u]) {
            continue;
        }
        if(u == des) {
            return;
        }
        for(int j = 1; j <= m; j++) {
            if((u & b2[j]) == 0 && (u & b1[j]) == b1[j]) {
                int v = (u & ~f1[j]) | f2[j];
                int w = weight[j];
                if(d[v] > d[u] + w) {
                    d[v] = d[u] + w;
                    que.push(make_pair(d[v], v));
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;
    for(int j = 1; j <= m; j++) {
        string b, f;
        cin >> weight[j] >> b >> f;

        for(int i = 0; i < n; i++) {
            if(b[i] == '+') {
                b1[j] |= (1 << i);
            } else if(b[i] == '-') {
                b2[j] |= (1 << i);
            }
            if(f[i] == '+') {
                f2[j] |= (1 << i);
            } else if(f[i] == '-') {
                f1[j] |= (1 << i);
            }
        }
    }
    dijkstra((1 << n) - 1, 0, m);
    int res = d[0];
    cout << (res == inf ? 0 : res) << "\n";
}

[CTSC1999]家园 - luogu P2754

Description
Sample Input

2 1
3 0 1 2
3 1 2 -1

Sample Output

Solution
可以发现，如果按时间拆点后枚举时间，那么第一次能够跑满流的层次，即使最短时间
因此魔改ISAP后暴力枚举加点加边，在残留网络中跑最大流即可
至于无解这个问题，实质上可以设置一个阈值，如到达这一阈值后还未满流则认为无解（算错阈值TLE了好几发 QAQ）

vector<int> hp[N];
int p[N], c[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    init();
    int n, m, k;
    cin >> n >> m >> k;
    int ss = N - 2, tt = N - 1;
    for(int i = 1, k; i <= m; i++) {
        cin >> c[i] >> k;
        while(k--) {
            int v;
            cin >> v;
            hp[i].push_back(v == -1 ? n + 1 : v);
        }
    }

    addEdge(ss, 0, k);
    int sum = 0;
    int ans = 0;
    for(int j = 0; j < 300; j++) {
        for(int i = 0 + j * (n + 2); i <= n + 1 + j * (n + 2); i++) {
            addEdge(i, i + (n + 2), inf);
        }
        for(int i = 1; i <= m; i++) {
            int u = hp[i][p[i]] + j * (n + 2);
            p[i] = (p[i] + 1) % hp[i].size();
            int v = hp[i][p[i]] + (j + 1) * (n + 2);
            addEdge(u, v, c[i]);
        }
        addEdge(n + 1 + (j + 1) * (n + 2), tt, inf);
        d[n + 1 + (j + 1) * (n + 2)] = 0;
        sum += ISAP(N - 5, ss, tt);
        if(sum == k) {
            ans = j + 1;
            break;
        }
    }
    cout << ans << "\n";
}

汽车加油行驶问题 - luogu P4009

Description
Sample Input

3 2 3 6
0 0 0 1 0 0 0 0
0 0 1 0 1 1 0 0
0 1 0 0 0 0 1 0
0 0 0 0 1 0 0 1
0 0 1 0 0 1 0 0
1 0 0 0 0 0 1 0
0 0 0 1 0 0 0 1
0 0 1 0 0 0 1 0
1 0 0 0 0 0 0 0

Sample Output

Solution
这是一道分层图最短路，到达每个点的最短路径与点的位置和剩余可走边数有关，因此分为k+1层

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int N = (int)100 + 2;
const int inf = 0x3f3f3f3f;

struct Point {
    int x, y, k, step;

    bool operator < (const Point& b) const {
        return step > b.step;
    }
};
int G[N][N], d[N][N][15];
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};

int solve(int n, int kk, int a, int b, int c) {
    memset(d, 0x3f, sizeof(d));
    d[1][1][kk] = 0;
    priority_queue<Point> que;
    que.push(Point{1, 1, kk, 0});
    while(!que.empty()) {
        Point ele = que.top();
        que.pop();

        int x = ele.x, y = ele.y, k = ele.k, step = ele.step;
        if(step > d[x][y][k]) {
            continue;
        }

        for(int j = 0; j < 4; j++) {
            int nx = x + dx[j], ny = y + dy[j];
            if(nx < 1 || ny < 1 || nx > n || ny > n) {
                continue;
            }
            int nv = step + (nx < x || ny < y) * b;
            if(nx == n && ny == n) {
                return nv;
            }
            if(G[nx][ny] == 0 && d[nx][ny][kk] > nv + a + c) {
                d[nx][ny][kk] = nv + a + c;
                que.push(Point{nx, ny, kk, d[nx][ny][kk]});
            }
            if(G[nx][ny] == 0 && k - 1 > 0 && d[nx][ny][k - 1] > nv) {
                d[nx][ny][k - 1] = nv;
                que.push(Point{nx, ny, k - 1, nv});
            }
            if(G[nx][ny] == 1 && d[nx][ny][kk] > nv + a) {
                d[nx][ny][kk] = nv + a;
                que.push(Point{nx, ny, kk, nv + a});
            }
        }
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, k, a, b, c;
    cin >> n >> k >> a >> b >> c;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            cin >> G[i][j];
        }
    }
    cout << solve(n, k, a, b, c) << "\n";
}

孤岛营救问题 - luogu P4011

Description
Sample Input

Sample Output

Solution
又是一道分层图最短路，而且还挺裸的

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int N = (int)11 + 2;
const int inf = 0x3f3f3f3f;

struct Point {
    int x, y, st;
};
int G[N][N];
int info[N][N][N][N];
int key[N][N];
int step[N][N][1 << N];
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};

int solve(int n, int m) {
    queue<Point> que;
    que.push(Point{1, 1, 0});
    while(!que.empty()) {
        Point ele = que.front();
        que.pop();

        if(ele.x == n && ele.y == m) {
            return step[ele.x][ele.y][ele.st];
        }

        for(int k = 0; k < 4; k++) {
            int nx = ele.x + dx[k];
            int ny = ele.y + dy[k];
            if(nx < 1 || ny < 1 || nx > n || ny > m || info[ele.x][ele.y][nx][ny] == -1 ||
               (info[ele.x][ele.y][nx][ny] && !(ele.st & info[ele.x][ele.y][nx][ny]))) {
                continue;
            }
            int nst = ele.st | key[nx][ny];
            if(step[nx][ny][nst]) {
                continue;
            }
            step[nx][ny][nst] = step[ele.x][ele.y][ele.st] + 1;
            que.push(Point{nx, ny, nst});
        }
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m, p, k;
    cin >> n >> m >> p >> k;
    while(k--) {
        int x1, y1, x2, y2, g;
        cin >> x1 >> y1 >> x2 >> y2 >> g;
        info[x1][y1][x2][y2] = info[x2][y2][x1][y1] = (g ? (1 << g) : -1);
    }
    cin >> k;
    while(k--) {
        int x, y, g;
        cin >> x >> y >> g;
        key[x][y] |= (1 << g);
    }
    cout << solve(n, m) << "\n";
}

数字梯形问题 - luogu P4013

Description
Sample Input

5
3
4 5
10 9 1
1 10 1 1
1 10 12 1 1

Sample Output

66
75
77

Solution
第一问：限制均不相交，意味着需要将点转为边并限制容量为1
第二问：允许在数字处相交，意味着可以把转为边的点的容量改为inf，这里注意要将连向T的点的容量也改为inf！
第三问：不拆点了直接跑（然而直接DP，岂不美哉？）

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;
    int sz = (2 * n + m - 1) * m / 2, ss = 0, tt = sz * 2 + 1;
    for(int i = 1, k = 0; i <= m; i++) {
        for(int j = 1; j <= i + n - 1; j++) {
            cin >> r[i][j];
            no[i][j] = ++k;
        }
    }

    init();
    for(int i = 1; i <= m; i++) {
        for(int j = 1; j <= i + n - 1; j++) {
            if(i == 1) {
                addEdge(ss, no[i][j], 1, 0);
            }
            if(i == m) {
                addEdge(no[i][j] + sz, tt, 1, 0);
            }
            addEdge(no[i][j], no[i][j] + sz, 1, -r[i][j]);
            if(i < m) {
                addEdge(no[i][j] + sz, no[i + 1][j], 1, 0);
                addEdge(no[i][j] + sz, no[i + 1][j + 1], 1, 0);
            }
        }
    }
    pair<ll, ll> res = solve(ss, tt, 2 * sz + 2);
    cout << -res.second << "\n";

    init();
    for(int i = 1; i <= m; i++) {
        for(int j = 1; j <= i + n - 1; j++) {
            if(i == 1) {
                addEdge(ss, no[i][j], 1, 0);
            }
            if(i == m) {
                addEdge(no[i][j] + sz, tt, inf, 0);
            }
            addEdge(no[i][j], no[i][j] + sz, inf, -r[i][j]);
            if(i < m) {
                addEdge(no[i][j] + sz, no[i + 1][j], 1, 0);
                addEdge(no[i][j] + sz, no[i + 1][j + 1], 1, 0);
            }
        }
    }
    res = solve(ss, tt, 2 * sz + 2);
    cout << -res.second << "\n";

    for(int i = m; i >= 1; i--) {
        for(int j = 1; j <= i + n - 1; j++) {
            r[i][j] += max(r[i + 1][j], r[i + 1][j + 1]);
        }
    }
    cout << accumulate(r[1] + 1, r[1] + n + 1, 0LL) << "\n";
}

运输问题 - luogu P4015

Description
Sample Input

Sample Output

48500
69140

Solution
仓库和商店一一连边，然后S和仓库连，T和商店连，跑MCMF完事，不贴代码

分配问题 - luogu P4014

Description
Sample Input

Sample Output

5
14

Solution
裸的二分图带权最大匹配，不贴代码

负载平衡问题 - luogu P4016

Description
Sample Input

5
17 9 14 16 4

Sample Output

Solution
！本题中位数才是正统解法
建图：
S -> {i}, cap = a[i] - avg, cost = 0: a[i] > avg，代表货物过多的点需要将多余的流走
{i} -> T, cap = avg - a[i], cost = 0: a[i] < avg，代表货物不足的点需要有货物流入
{i} -> {i-1, i+1}, cap = inf, cost = 1：代表货物可中转
跑MCMF即可

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    init();
    int ss = 0, tt = n + 1;
    int avg = accumulate(a + 1, a + 1 + n, 0) / n;
    for(int i = 1; i <= n; i++) {
        if(a[i] < avg) {
            addEdge(i, tt, avg - a[i], 0);
        } else if(a[i] > avg) {
            addEdge(ss, i, a[i] - avg, 0);
        }
        addEdge(i, i % n + 1, inf, 1);
        addEdge(i, (i + n - 2) % n + 1, inf, 1);
    }
    pair<ll, ll> res = solve(ss, tt, n + 2);
    cout << res.second << "\n";
}

火星探险问题 - luogu P3356

Description
Sample Input

2
10
8
0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0
0 0 1 0 2 0 0 0 0
1 0 1 2 0 0 0 0 1
1 0 0 2 0 1 1 0 0
1 0 1 0 0 1 1 0 0
1 2 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0

Sample Output

Solution
拆点为边，障碍点不建边，石块多建一条cost=-1,cap=1的边，其余正常操作
输出方案只需要沿有流量的路DFS即可

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    init();
    int k, n, m;
    cin >> k >> m >> n;
    int sz = n * m, ss = 0, tt = sz * 2;
    addEdge(ss, 1, k, 0);
    for(int i = 1, tot = 0; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> G[i][j];
            no[i][j] = ++tot;
            if(G[i][j] == 0) {
                addEdge(no[i][j], no[i][j] + sz, inf, 0);
            }
            if(G[i][j] == 2) {
                addEdge(no[i][j], no[i][j] + sz, inf, 0);
                addEdge(no[i][j], no[i][j] + sz, 1, -1);
            }
            if(i - 1 >= 1) {
                addEdge(no[i - 1][j] + sz, no[i][j], inf, 0);
            }
            if(j - 1 >= 1) {
                addEdge(no[i][j - 1] + sz, no[i][j], inf, 0);
            }
        }
    }
    auto res = solve(ss, tt, tt + 1);

    for(int p = 1; p <= res.first; p++) {
        int u = 1 + sz;
        while(u != tt) {
            for(int i = head[u]; ~i; i = e[i].nxt) {
                int v = e[i].v;
                if(e[i].flow < e[i].cap && v > u - sz) {
                    int dir = (v == u - sz + 1);
                    cout << p << " " << dir << "\n";
                    e[i].flow++;
                    u = v + sz;
                    break;
                }
            }
        }
    }
}

最长k可重区间集问题 - luogu P3358

Description
Sample Input

Sample Output

Solution
建图
S -> {1}, cap = k, cost = 0
{i} -> {i + 1}, cap = inf, cost = 0
{li} -> {ri}, cap = 1, cost = -(ri - li)
{N} -> T, cap = k, cost = 0
可以这样想，流最大只会是k，那么其一定会优先分流到费用小的边上去，使得总费用变小（关键在于分流）

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, k;
    cin >> n >> k;
    for(int i = 1; i <= n; i++) {
        cin >> l[i] >> r[i];
        mp[i] = l[i];
        mp[i + n] = r[i];
    }
    sort(mp + 1, mp + 1 + 2 * n);
    int m = unique(mp + 1, mp + 1 + 2 * n) - mp - 1;

    init();
    int ss = 0, tt = m + 1;
    for(int i = 1; i <= n; i++) {
        int u = lower_bound(mp + 1, mp + 1 + m, l[i]) - mp;
        int v = lower_bound(mp + 1, mp + 1 + m, r[i]) - mp;
        addEdge(u, v, 1, -r[i] + l[i]);
    }
    for(int i = 1; i < m; i++) {
        addEdge(i, i + 1, inf, 0);
    }
    addEdge(ss, 1, k, 0);
    addEdge(m, tt, k, 0);
    auto res = solve(ss, tt, tt + 1);
    cout << -res.second << "\n";
}