网络流 24 题

时间：2020-02-29 01:59:25 阅读：56 评论：0 收藏：0 [点我收藏+]

飞行员配对方案问题

题目链接。二分图匹配模板。

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 105;
int n, m, match[N];
int head[N], numE = 0;
bool vis[N];
struct E{
    int next, v;
} e[N * N];
void add(int u, int v) {
    e[++numE] = (E) { head[u], v };
    head[u] = numE;
}
bool find(int u) {
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].v;
        if (vis[v]) continue;
        vis[v] = true;
        if (!match[v] || find(match[v])) {
            match[v] = u; return true;
        }
    }
    return false;
}

int main() {
    scanf("%d%d", &n, &m);
    int u, v;
    while (scanf("%d%d", &u, &v), v != -1) 
        add(u, v - n);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        memset(vis, false, sizeof vis);
        if (find(i)) ans++;
    }
    printf("%d\n", ans);
    for (int i = 1; i <= m; i++)
        if (match[i]) printf("%d %d\n", match[i], i + n);
}

太空飞行计划问题

题目链接。是一个最大权闭合图问题。这问题的证明真是太神仙了，构造网络的方式：

起点向实验连一条流量为费用的边
实验向仪器连流量为无限的边
仪器向终点连流量为费用的边

由于证明很抽象，自己有一个突发奇想感性的理解：

由于中间连的是无限流量，所以限制肯定在两边。
假如一个实验它的流量流完了，说明他的费用不比它小，那么留着它就是祸患，所以可以它的答案有删除的贡献
加入一个实验留了一部分，这一部分失去的其实就是仪器费用，有删除的贡献
由于最大流 / 最小割是个实时更新残余网络的算法，所以可以实时解决问题。

所以答案就是实验总费用 $-$ 最小割。输出方案源自证明的过程，即起点这边联通块实际就是一个最大权闭合图。

#include <cstdio>
#include <iostream>
#include <sstream>
#include <string>
#include <cstring>
using namespace std;
const int N = 55, L = N * 2, INF = 1e9;
int m, n, s, t, p[N], c[N], d[L], q[L], sum;
int head[L], numE = 1, flow, maxflow;
string g;
struct E{
    int next, v, w;
} e[N * N + 4 * N];
void add(int u, int v, int w) {
    e[++numE] = (E) { head[u], v, w };
    head[u] = numE;
}
void addEdge(int u, int v, int w) {
    add(u, v, w); add(v, u, 0);
}

bool bfs() {
    memset(d, 0, sizeof d);
    int hh = 0, tt = 0;
    d[s] = 1, q[0] = s;
    while (hh <= tt) {
        int u = q[hh++];
        for (int i = head[u]; i; i = e[i].next) {
            int v = e[i].v;
            if (!d[v] && e[i].w) {
                d[v] = d[u] + 1;
                q[++tt] = v;
                if (v == t) return true;
            }
        }
    }
    return false;
}

int dinic(int u, int flow) {
    if (u == t) return flow;
    int rest = flow;
    for (int i = head[u]; i && rest; i = e[i].next) {
        int v = e[i].v;
        if (e[i].w && d[v] == d[u] + 1) {
            int k = dinic(v, min(rest, e[i].w));
            if (!k) d[v] = 0;
            e[i].w -= k, e[i ^ 1].w += k;
            rest -= k;
        }
    }
    return flow - rest;
}

int main() {
    scanf("%d%d\n", &m, &n);
    s = n + m + 1, t = n + m + 2;
    for (int i = 1; i <= m; i++) {
        getline(cin, g); stringstream sin(g);
        sin >> p[i]; addEdge(s, i, p[i]); sum += p[i];
        int x;
        while (sin >> x) addEdge(i, x + m, INF);
    }
    for (int i = 1; i <= n; i++)
        scanf("%d", c + i), addEdge(i + m, t, c[i]);
    while (bfs())
        while(flow = dinic(s, INF)) maxflow += flow;
    for (int i = 1; i <= m; i++) if(d[i]) printf("%d ", i);
    puts("");
    for (int i = 1; i <= n; i++) if(d[i + m]) printf("%d ", i);
    printf("\n%d\n", sum - maxflow);
    return 0;
}

最小路径覆盖问题

题目链接 ~~能用二分图算法就不用网络流~~。根据定理，在拆点二分图上最小路径覆盖 $= $ 总数 $-$ 二分图最大匹配。

输出路径，这次不能用那个技巧了，但通过定理的推导我们知道左侧非匹配点和路径终点是一一对应的，我们只要从非匹配点出发倒序递推每条路径就行了。

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 155, M = 6005;
int n, m, match[N];
int head[N], numE = 0;
bool vis[N], st[N];
struct E{
    int next, v;
} e[M];
void add(int u, int v) {
    e[++numE] = (E) { head[u], v };
    head[u] = numE;
}

bool find(int u) {
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].v;
        if (vis[v]) continue;
        vis[v] = true;
        if (!match[v] || find(match[v])) {
            match[v] = u; return true;
        }
    }
    return false;
}
void print(int x) {
    if (x == 0) return;
    print(match[x]);
    printf("%d ", x);
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v; i <= m; i++)
        scanf("%d%d", &u, &v), add(u, v);
    int ans = n;
    for (int i = 1; i <= n; i++) {
        memset(vis, false, sizeof vis);
        if (find(i)) ans--;
        else st[i] = true;
    }
    for (int i = 1; i <= n; i++) 
        if (st[i]) print(i), puts("");
    printf("%d\n", ans);
}

魔术球问题

题目链接。模拟题意，每次扩大编号，尝试是否可行。转换模型，将编号中两点间是完全平方数的，由编号大的向小的连一条边，很显然这是个 DAG。

即在 DAG 上用最少的路径（不相交）覆盖所有的点。根据定理，在拆点二分图上最小路径覆盖 $= $ 总数 $-$ 二分图最大匹配，当路径覆盖 $ > n$ 时，即可停止。输出方案，因为我们找增广路都是从新增的往前找，所以每条路径的终点一定是最小的，从小到大一次考虑没访问的点，不断递归它的匹配点（由定理的证明过程我们知道匹配边都是一条路径的边）直到无法跳为止。

那个点边的最大值是自测最大数据找的极值。

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
const int N = 1570, M = 18000;
int K, n, res = 0, match[N];
int head[N], numE = 0;
bool vis[N];
struct E{
    int next, v;
} e[M];
void add(int u, int v) {
    e[++numE] = (E) { head[u], v };
    head[u] = numE;
}
bool find(int u) {
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].v;
        if (vis[v]) continue;
        vis[v] = true;
        if (!match[v] || find(match[v])) {
            match[v] = u; return true;
        }
    }
    return false;
}
int main() {
    int cnt = 0;
    scanf("%d", &K);
    for (n = 1; ; n++) {
        for (int i = sqrt(n) + 1; i * i < 2 * n; i++) add(n, i * i - n);
        if (find(n)) res++;
        memset(vis, false, sizeof vis);
        if (n - res > K) break;
    }
    printf("%d\n", --n);
    for (int i = 1; i <= n; i++)
        if (!vis[i]) {
            for (int j = i; j; j = match[j]) printf("%d ", j), vis[j] = true;
            puts("");
        }
    return 0;
}

圆桌问题

题目链接。二分图多重匹配问题：

让起点连单位代表，流量为 $r$
由于同一单位不能再同一餐桌，所以每个单位朝每个餐桌连边，流量为 $1$
餐桌向终点连边，流量为 $c$

输出方案：看一下单位向餐桌的边哪条空了即可（流完了）。

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int M = 155, N = 275, INF = 1e9;
int m, n, s, t, q[M + N], d[M + N], sum;
int head[M + N], numE = 1;
struct E{
    int next, v, w;
} e[(M * N + M + N) * 2];
void add(int u, int v, int w) {
    e[++numE] = (E) { head[u], v, w };
    head[u] = numE;
}
void addEdge(int u, int v, int w) {
    add(u, v, w), add(v, u, 0);
}
bool bfs() {
    memset(d, 0, sizeof d);
    int hh = 0, tt = 0;
    q[0] = s, d[s] = 1;
    while (hh <= tt) {
        int u = q[hh++];
        for (int i = head[u]; i; i = e[i].next) {
            int v = e[i].v;
            if (!d[v] && e[i].w) {
                d[v] = d[u] + 1;
                q[++tt] = v;
                if (v == t) return true;
            }
        }
    }
    return false;
}

int dinic(int u, int flow) {
    if (u == t) return flow;
    int rest = flow;
    for (int i = head[u]; i && rest; i = e[i].next) {
        int v = e[i].v;
        if (d[v] == d[u] + 1 && e[i].w) {
            int k = dinic(v, min(rest, e[i].w));
            if (!k) d[v] = 0;
            e[i].w -= k, e[i ^ 1].w += k;
            rest -= k;
        }
    }
    return flow - rest;
}

int main() {
    scanf("%d%d", &m, &n);
    s = m + n + 1, t = m + n + 2;
    for (int i = 1, r; i <= m; i++) 
        scanf("%d", &r), sum += r, addEdge(s, i, r);
    for (int i = 1, c; i <= n; i++)
        scanf("%d", &c), addEdge(i + m, t, c);
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++) addEdge(i, j + m, 1);
    int flow, maxflow = 0;
    while (bfs())
        while (flow = dinic(s, INF)) maxflow += flow;
    if (maxflow != sum) puts("0");
    else {
        puts("1");
        for (int u = 1; u <= m; u++) {
            for (int i = head[u]; i; i = e[i].next) {
                int v = e[i].v;
                if (v != s && !e[i].w) printf("%d ", v - m);
            }
            puts("");
        }
    }
}

最长不下降子序列问题

题目链接。（第一次见这种题不会建图。。只好看题解，然后发现是我题读错了。）

第一问

设 $f[i]$ 以 $i$ 结尾的最长不下降子序列，dp即可。

第二问

用分层图的思想，把 $f[i]$ 按照值划分成 $s$ 个不同的值。

由于每个点只能在一个序列的原则，拆点限制，把 $i$ 拆成一个入点和一个出点，入点向出点连流量为 $1$ 的边
由起点向每一个 $f[i] = 1$ 的点连 $1$ 的流量。
由每一个 $f[i] = s$ 的点向终点连 $1$ 的流量。
将能够转移的 $i, j$ （即 $i < j, f[i] + 1 = f[j]$ ）连一条边

每一条从起点到终点的路径都是一个长度为 $s$ 的最长不下降子序列。

这样去除最多的序列等价于找到最多的从 $s, t$ 互不干扰的路径，这里流量为 $1$，最大流和它们是等价的。

第三问

与第二问不同的就是两个可以反复使用，所以把 $1, n$ 所在内部入点出点的边流量设为无限，并且如果它们与起点终点连过边，流量也设为无限。这样既设计为除了 $1, n$，剩下点只能经过一次，和题目等价。有个小技巧，改变流量可以直接加流量，跑最大流不用重新跑一遍，加一条边可以在上次的残余网络上跑。

并且要注意一个特例就是 $n = 1$ 的情况，这时候不能起点向 $1$ 连边，否则就输出 $INF$ 了。

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 505, L = N * 2, M = N * (N - 1) + N * 2, INF = 1e9;
int n, S, s, t, a[N], f[N], d[L], q[L], maxflow, flow;
int head[L], numE = 1;
struct E{
    int next, v, w;
} e[M];
void add(int u, int v, int w) {
    e[++numE] = (E) { head[u], v, w };
    head[u] = numE;
} 
void addEdge(int u, int v, int w) {
    add(u, v, w), add(v, u, 0);
}
bool bfs() {
    memset(d, 0, sizeof d);
    int hh = 0, tt = 0;
    q[0] = s, d[s] = 1;
    while (hh <= tt) {
        int u = q[hh++];
        for (int i = head[u]; i; i = e[i].next) {
            int v = e[i].v;
            if (!d[v] && e[i].w) {
                d[v] = d[u] + 1;
                q[++tt] = v;
                if (v == t) return true;
            }
        }
    }
    return false;
} 
int dinic(int u, int flow) {
    if (u == t) return flow;
    int rest = flow;
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].v;
        if (d[v] == d[u] + 1 && e[i].w) {
            int k = dinic(v, min(rest, e[i].w));
            if (!k) d[v] = 0;
            e[i].w -= k, e[i ^ 1].w += k;
            rest -= k;
        }
    }
    return flow - rest;
}
int main() {
    scanf("%d", &n);
    s = 2 * n + 1, t = 2 * n + 2;
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    for (int i = 1; i <= n; i++) {
        f[i] = 1;
        for (int j = 1; j < i; j++) 
            if (a[j] <= a[i]) f[i] = max(f[i], f[j] + 1);
        S = max(S, f[i]);
    }
    printf("%d\n", S);
    for (int i = 1; i <= n; i++) {
        addEdge(i, i + n, 1);
        if (f[i] == 1) addEdge(s, i, 1);
        if (f[i] == S) addEdge(i + n, t, 1);
        for (int j = 1; j < i; j++)
            if (a[j] <= a[i] && f[j] + 1 == f[i]) addEdge(j + n, i, 1);
    }
    while (bfs())
        while (flow = dinic(s, INF)) maxflow += flow;
    printf("%d\n", maxflow);
    
    if (S != 1) addEdge(s, 1, INF), addEdge(1, 1 + n, INF);
    if (f[n] == S) addEdge(n * 2, t, INF), addEdge(n, n * 2, INF);
    while (bfs())
        while (flow = dinic(s, INF)) maxflow += flow;
    printf("%d\n", maxflow);
}

试题库问题

题目链接。把题和类别分别放左右两边，把能匹配的题和类型中间连边，是二分图，我们求的是二分图的多重匹配。多重匹配最优解法即建网络，根据题意设计起点到题的流量为 $1$，题和类型的流量也是 $1$，类型到终点的流量是读入要选出的题数，跑最大流即可。输出方案，看二分图中间的边哪条被流过的即可。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int N = 1025, S = 25, INF = 1e9;
int K, n, m, s, t, d[N], q[N], maxflow, flow;
int head[N], numE = 1;
vector<int> ans[S];
struct E{
    int next, v, w;
} e[(N * S + N + S) << 1];
void add(int u, int v, int w) {
    e[++numE] = (E) { head[u], v, w };
    head[u] = numE;
}
void addEdge(int u, int v, int w) {
    add(u, v, w), add(v, u, 0);
}

bool bfs() {
    memset(d, 0, sizeof d);
    int hh = 0, tt = 0;
    d[s] = 1, q[0] = s;
    while (hh <= tt) {
        int u = q[hh++];
        for (int i = head[u]; i; i = e[i].next) {
            int v = e[i].v;
            if (e[i].w && !d[v]) {
                d[v] = d[u] + 1;
                q[++tt] = v;
                if (v == t) return true;
            }
        }
    }
    return false;
}

int dinic(int u, int flow) {
    if (u == t) return flow;
    int rest = flow;
    for (int i = head[u]; i && rest; i = e[i].next) {
        int v = e[i].v;
        if (e[i].w && d[v] == d[u] + 1) {
            int k = dinic(v, min(flow, e[i].w));
            if (!k) d[v] = 0;
            e[i].w -= k, e[i ^ 1].w += k;
            rest -= k;
        }
    }
    return flow - rest;
}

int main() {
    scanf("%d%d", &K, &n);
    s = n + K + 1, t = n + K + 2;
    for (int i = 1, x; i <= K; i++)
        scanf("%d", &x), addEdge(n + i, t, x), m += x;
    for (int i = 1, p, x; i <= n; i++) {
        scanf("%d", &p); addEdge(s, i, 1);
        while (p--) scanf("%d", &x), addEdge(i, n + x, 1);
    }
    while (bfs())
        while (flow = dinic(s, INF)) maxflow += flow;
    if (maxflow != m) puts("No Solution!");
    else {
        for (int u = 1; u <= n; u++) {
            for (int i = head[u]; i; i = e[i].next) {
                int v = e[i].v;
                if (v != s && !e[i].w) ans[v - n].push_back(u);
            }
        }
        for (int i = 1; i <= K; i++) {
            printf("%d:", i);
            for (int j = 0; j < ans[i].size(); j++) printf(" %d", ans[i][j]);
            puts("");
        }
    }
}

机器人路径规划问题

题目链接。据说是一道假题？

方格取数问题

题目链接

这个构造方式也是始料不及的。把相邻有矛盾的点连上边，这显然是一个二分图。考虑答案求的是删除最少的带权点使得二分图没有边。即可以建网络，一个点到起点 / 终点的流量是他本身的权值。

要取出的数总权最大，就要让删的最少。要删除点的数量总权值最少 $\Leftrightarrow$ 最小割 $\Leftrightarrow$ 最大流。最后用总数减最大流即可。

复杂度：边数 $n * m$ 级别，点数 $n * m$ 级别，跑 Dinic 复杂度 $O(NM\sqrt{NM})$

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 105;
typedef long long LL;
const LL INF = 1e18;
int n, m, s, t, a[N][N], d[N * N], q[N * N];
int head[N * N], numE = 1;
LL flow, maxflow, sum;
struct E{
    int next, v;
    LL w;
} e[N * N * 4];
void add(int u, int v, LL w) {
    e[++numE] = (E) { head[u], v, w };
    head[u] = numE;
}
void addEdge(int u, int v, LL w) {
    add(u, v, w); add(v, u, 0);
}

bool bfs() {
    memset(d, 0, sizeof d);
    int hh = 0, tt = 0;
    q[0] = s, d[s] = 1;
    while (hh <= tt) {
        int u = q[hh++];
        for (int i = head[u]; i; i = e[i].next) {
            int v = e[i].v;
            if (!d[v] && e[i].w) {
                d[v] = d[u] + 1;
                q[++tt] = v;
                if (v == t) return true;
            }
        }
    }
    return false;
}

LL dinic(int u, LL flow) {
    if (u == t) return flow;
    LL rest = flow;
    for (int i = head[u]; i && rest; i = e[i].next) {
        int v = e[i].v;
        if (e[i].w && d[v] == d[u] + 1) {
            LL k = dinic(v, min(rest, e[i].w));
            if (!k) d[v] = 0;
            e[i].w -= k, e[i ^ 1].w += k;
            rest -= k;
        }
    }
    return flow - rest;
}

int num(int i, int j) { return (i - 1) * m + j; }

int main() {
    scanf("%d%d", &n, &m);
    s = n * m + 1, t = n * m + 2;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &a[i][j]); sum += a[i][j];
            if ((i + j) & 1) {
                addEdge(s, num(i, j), a[i][j]);
                if (i > 1) addEdge(num(i, j), num(i - 1, j), INF);
                if (i < n) addEdge(num(i, j), num(i + 1, j), INF);
                if (j > 1) addEdge(num(i, j), num(i, j - 1), INF);
                if (j < m) addEdge(num(i, j), num(i, j + 1), INF);
            } else {
                addEdge(num(i, j), t, a[i][j]);
            }
        }
    }
    while (bfs())
        while (flow = dinic(s, INF)) maxflow += flow;
    printf("%lld\n", sum - maxflow);

}

餐巾计划问题

题目链接。瞪眼半天还是不会，我枯了。

显然每天有两个状态转移时刻，一个是一个是每天开始前 $a_0$（需求干净毛巾），每天结束时 $a_1$（提供脏毛巾的处理）：

买新毛巾 $s$ → $a_0$，流量无限，费用为 $p$
快洗 $a_1$ → $(a + m)_0$，流量无限，费用为 $f$
慢洗 $a_1$ → $(a + n)_0$，流量无限，费用为 $s$
延期送洗 $a_1$ → $(a + 1)_1$，流量无限，费用为 $0$
每天结束后，餐厅会生产和求等量的脏餐巾：$s$ → $a_1$，流量为 $r[a]$，费用为 $0$
每天开始时，需要提交 $r[i]$ 个餐巾，提交方式给汇点： $a_0$ 箭头 $t$，流量为 $r[a]$，费用为 $0$

在任何边上的流量，相当于一个餐巾被执行了相应的过程，并且花费一定的费用，要求是跑完最大流（满足所有条件），且费用最小。显然肯定有能满足所有条件（不够可以买买买），所以我们跑最小费用最大流。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#define x first
#define y second
using namespace std;
typedef long long LL;
const int N = 2005, INF = 2e9;
typedef pair<LL, int> PII;
int n, s, t, c[N], c0, m1, c1, m2, c2;
LL ans, incf[N << 1], dis[N << 1];
int pre[N << 1];
int head[N << 1], numE = 1;
bool vis[N << 1];
priority_queue<PII, vector<PII>, greater<PII> > q;
struct E{
    int next, v, w, c;
} e[N * 12];
void add(int u, int v, int w, int c) {
    e[++numE] = (E) { head[u], v, w, c };
    head[u] = numE;
}
void addEdge(int u, int v, int w, int c) {
    add(u, v, w, c), add(v, u, 0, -c);
}
bool dijkstra() {
    memset(dis, 0x3f, sizeof dis);
    memset(vis, false, sizeof vis);
    while (!q.empty()) q.pop();
    dis[s] = 0, q.push(make_pair(0, s));
    incf[s] = INF;
    while (!q.empty()) {
        PII u = q.top(); q.pop();
        if (vis[u.y]) continue;
        vis[u.y] = true;
        for (int i = head[u.y]; i; i = e[i].next) {
            int v = e[i].v;
            if (e[i].w && dis[u.y] + e[i].c < dis[v]) {
                dis[v] = dis[u.y] + e[i].c;
                incf[v] = min((LL)e[i].w, incf[u.y]);
                pre[v] = i;
                q.push(make_pair(dis[v], v));
                if (v == t) return true;
            }
        }
    } 
    return false;
}

void update() {
    int x = t;
    while (x != s) {
        int i = pre[x];
        e[i].w -= incf[t], e[i ^ 1].w += incf[t];
        x = e[i ^ 1].v;
    }
    ans += incf[t] * dis[t];
}

int main() {
    scanf("%d", &n);
    s = n * 2 + 1, t = n * 2 + 2;
    for (int i = 1; i <= n; i++) scanf("%d", c + i);
    scanf("%d%d%d%d%d", &c0, &m1, &c1, &m2, &c2);
    for (int i = 1; i <= n; i++) {
        addEdge(s, i, INF, c0);
        if (i + m1 <= n) addEdge(i + n, i + m1, INF, c1);
        if (i + m2 <= n) addEdge(i + n, i + m2, INF, c2);
        if (i < n) addEdge(i + n, i + n + 1, INF, 0);
        addEdge(s, i + n, c[i], 0);
        addEdge(i, t, c[i], 0);
    }
    while (dijkstra()) update();
    printf("%lld\n", ans);
}

航空路线问题

这题的限制是每个点只能经过一次，而网络流做到的是边的限制，考虑点边转换把每个点拆成入点 $A_i$和出点 $B_i$：

找到一条 $1$ → $n$ → $1$ 路径，等价于两条 $1$ → $n$ 的不相交路径，要求经过点最多，建立费用流模型：

$A_i$ → $B_i$ 流量为 1（若 $i = 1$ 或 $n$ 流量为 $2$)，费用为 $1$
一条边 $(u, v)$，$B_u$ → $A_v$ 流量为 $1$（若 $1$ → $n$ 则为 $2$），费用为 $0$

方案 $dfs$ 跑零流边求解。（ $dfs$ 复杂度 $O(n)$ 的，找到一条路径就 break）

我太菜了，循环队列写不对。。

#include <cstdio>
#include <iostream>
#include <string>
#include <unordered_map>
#include <cstring>
using namespace std;
const int N = 105, L = N << 1, INF = 0x3f3f3f3f;
unordered_map<string, int> S;
int n, m, s, t, q[L], dis[L], incf[L], pre[L];
int ans[L], tot = 0, maxflow = 0;
string a, b, g[N];
int head[L], numE = 1, sum = 0;
bool vis[L];
struct E{
    int next, v, w, c;
} e[N * N + N * 2];
void add(int u, int v, int w, int c) {
    e[++numE] = (E) { head[u], v, w, c };
    head[u] = numE;
}
void inline addEdge(int u, int v, int w, int c) {
    add(u, v, w, c); add(v, u, 0, -c);
}
bool spfa() {
    memset(dis, -0x3f, sizeof dis);
    int hh = 0, tt = 1;
    q[0] = s, dis[s] = 0, incf[s] = INF;
    while (hh != tt) {
        int u = q[hh++];
        if (hh == L) hh = 0;
        vis[u] = false;
        for (int i = head[u]; i; i = e[i].next) {
            int v = e[i].v;
            if (e[i].w && dis[u] + e[i].c > dis[v]) {
                dis[v] = dis[u] + e[i].c;
                incf[v] = min(incf[u], e[i].w);
                pre[v] = i;
                if (!vis[v]) {
                    vis[v] = true, q[tt++] = v;
                    if (tt == L) tt = 0;
                }
            }
        }
    }
    return dis[t] != dis[0];
}

void update() {
    int x = t;
    while (x != s) {
        int i = pre[x];
        e[i].w -= incf[t], e[i ^ 1].w += incf[t];
        x = e[i ^ 1].v;
    }
    sum += dis[t] * incf[t];
    maxflow += incf[t];
}

void dfs(int u) {
    vis[u] = true;
    ans[++tot] = u;
    for (int i = head[u + n]; i; i = e[i].next) {
        int v = e[i].v;
        if (v <= n && !vis[v] && !e[i].w) {
            dfs(v);
            break;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    s = 1, t = n * 2;
    for (int i = 1; i <= n; i++) cin >> g[i], S[g[i]] = i;
    for (int i = 1; i <= n; i++) addEdge(i, i + n, (i == 1 || i == n) ? 2 : 1, 1);
    for (int i = 1; i <= m; i++) {
        cin >> a >> b;
        int x = S[a], y = S[b];
        if (x > y) swap(x, y);
        addEdge(x + n, y, (x == 1 && y == n) ? 2 : 1, 0);
    }
    while (spfa()) update();
    if (maxflow < 2) {
        cout << "No Solution!" << endl;
        return 0;
    }
    cout << sum - 2 << endl;
    dfs(1);
    for (int i = 1; i <= tot; i++) cout << g[ans[i]] << endl;
    tot = 0;
    dfs(1);
    for (int i = tot; i; i--) cout << g[ans[i]] << endl;
    return 0;
}

软件补丁问题

题目链接。我自闭了，题目都没看懂，样例一脸懵逼，后来发现是把 B1, B2 看反了。

看到 $n <= 20$，想到装压，可以设一个二进制状态 $S$ ，若当前这一位是 $1$ 则修复成功状态，反之则是错误，即起始状态是 $0$，目标状态为 $111111111...$

对于一个状态 $S$，枚举每一个操作 $i$：

根据定义，若 $B1[i]\ \cup\ S = 0$ 且 $B2[i]\ \cup\ S = B2[i]$，则可以进行这次操作:

即状态 $S$ 转移至 $S\ \cup \complement_\cup F21[i]\ \cap F1[i]$，代价为 $t$。

显然每一种成功的操作等价于一条从起点到终点的路径，要求代价最少，最短路即可（网络流与这题的关系：让每条路径流量为 $1$ 即为网络流。。）

复杂度玄学。（第一次建边 $MLE$ 了）

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 20, M = 100, L = 1 << N, INF = 0x3f3f3f3f;
int n, m, s = 0, t, q[1 << N], dis[1 << N], B1[M], B2[M], F1[M], F2[M], c[M];
int head[1 << N], numE = 0;
bool vis[1 << N];
char g[N];
// + 属于 a, - 属于 b
void work(int &a, int &b) {
    for (int i = 0; i < n; i++)
        if (g[i] == '+') a |= 1 << i;
        else if(g[i] == '-') b |= 1 << i;
}

int spfa() {
    int hh = 0, tt = 1;
    memset(dis, 0x3f, sizeof dis);
    q[0] = s, dis[s] = 0;
    while (hh != tt) {
        int u = q[hh++]; vis[u] = false;
        if (u == L) hh = 0;
        for (int j = 0; j < m; j++) {
            if ((u & B1[j]) == 0 && (u & B2[j]) == B2[j]) {
                int v = ((u & (~F2[j] & t)) | F1[j]), w = c[j];
                if (dis[u] + w < dis[v]) {
                    dis[v] = dis[u] + w;
                    if (!vis[v]) {
                        vis[v] = true, q[tt++] = v;
                        if (tt == L) tt = 0;
                    }
                }
            }
        }
    }
    return dis[t] == INF ? 0 : dis[t];
}


int main() {
    scanf("%d%d", &n, &m);
    t = (1 << n) - 1;
    for (int i = 0; i < m; i++) {
        scanf("%d%s", c + i, g);
        work(B1[i], B2[i]);
        scanf("%s", g);
        work(F2[i], F1[i]);
    }
    printf("%d\n", spfa());
}

星际转移问题

题目链接。~~太菜了不会又去看题解~~。

隐约的感知到，每个人从地球到月球从图论的角度上来说构成一条路径，每个人又可以抽象成单位 $1$ 的流，所以这题就是网络流？但是由于天数时间轴的影响不能直接建图。所以这题解启示我们建立分层图，即某天的一个位置抽象为为一个图中的节点。

题意中的两种决策乘坐飞船、下船等待可以抽象成两种边（由于具有传递性所以只需连接一步操作的节点）。不过还要注意的是每天地球和月球的边要注意和源点和汇点进行联系，进而达到图题一体的模式。

乘坐飞船走：对于一条飞船上的路径，一天对应位置的节点 $\Rightarrow$ 后一天对应位置的节点，流量为 $H[i]$ ，表示通过这种方式最多可以送走 $H[i]$ 人
下船等待：某位置一天的节点 $\Rightarrow$ 下一天同一位置的节点，流量无限
源点向每天的地球连边无限，每天月球向汇点连接无限

发现二分复杂度是冗余的，不妨从小到大枚举时间。

考虑存在情况的最坏情况下的时间，一条路径肯定没有环（不然可以不走环），所以一条链最长有 $m + 2$ 个点， $m + 1$ 条边，可能一个循环才能跑一次，所以每转移一条边 $n + 2$ 个时间。所以时间最多 $(m + 2) * (n + 2) <= 330$，所以枚举到 $330$ 就行了。。总复杂度 $(N + M + 11500 * \sqrt{4950})$，~~一看就跑得很快~~。（这里的复杂度由于边加边边在残余网络上跑，所以貌似是这个复杂度 # 我也不确定）

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 14, M = 21, S = 55, L = 5000, INF = 1e9, LM = 23500;
int n, m, s, t, K, p[M], r[M], h[M][N + 2], q[L], d[L], maxflow, flow;
int head[L], numE = 1;
struct E{
    int next, v, w;
} e[LM];
void add(int u, int v, int w) {
    e[++numE] = (E) { head[u], v, w };
    head[u] = numE;
}
void addEdge(int u, int v, int w) {
    add(u, v, w); add(v, u, 0);
}

bool bfs() {
    memset(d, 0, sizeof d);
    int hh = 0, tt = 0;
    q[0] = s, d[s] = 1;
    while (hh <= tt) {
        int u = q[hh++];
        for (int i = head[u]; i; i = e[i].next) {
            int v = e[i].v;
            if (e[i].w && !d[v]) {
                d[v] = d[u] + 1;
                q[++tt] = v;
                if (v == t) return true;
            }
        }
    }
    return false;
}

int dinic(int u, int flow) {
    if (u == t) return flow;
    int rest = flow;
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].v;
        if (e[i].w && d[v] == d[u] + 1) {
            int k = dinic(v, min(rest, e[i].w));
            if (!k) d[v] = 0;
            e[i].w -= k, e[i ^ 1].w += k;
            rest -= k;
        }
    }
    return flow - rest;
}

//  第 i 天，第 j 号飞船
int get(int i, int j) {
    if (j == 0) return 3 + i * (n + 2);
    else if(j == -1) return 4 + i * (n + 2);
    return 4 + i * (n + 2) + j;
}


void build(int i) {
    int cnt = 2 + i * (n + 2);
    int st = cnt + 1, ed = cnt + 2;
    addEdge(s, st, INF), addEdge(ed, t, INF);
    for (int j = 1; j <= n; j++) addEdge(get(i - 1, j), get(i, j), INF);
    for (int j = 0; j < m; j++) {
        int u = h[j][(i - 1) % r[j]], v = h[j][i % r[j]];
        addEdge(get(i - 1, u), get(i, v), p[j]);
    }
}

int main() {
    scanf("%d%d%d", &n, &m, &K);
    s = 1, t = 2;
    // 第 0 天的地球和月亮连边
    addEdge(1, 3, INF), addEdge(4, 2, INF);
    for (int i = 0; i < m; i++) {
        scanf("%d%d", p + i, r + i);
        for (int j = 0; j < r[i]; j++) scanf("%d", &h[i][j]);
    }
    for (int t = 1; t <= 330; t++) {
        build(t);
        while (bfs())
            while(flow = dinic(s, INF)) maxflow += flow;
        if (maxflow >= K) {
            printf("%d\n", t);
            return 0;
        }
    }
    puts("0");
    return 0;
}

孤岛营救问题

题目链接

这次跑分层图 $bfs$ 即可。

#include <cstdio>
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int INF = 2e9;
const int N = 11;
int n, m, P, K, S, g[N][N];
int w[N][N][4], dis[N][N][1 << N];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
bool vis[N][N][1 << N];
struct Node{
    int x, y, s, d;
    bool operator < (const Node &x) const {
        return d > x.d;
    }
};
priority_queue<Node> q;
// { 上下左右 }
int inline dijkstra() {
    memset(dis, 0x3f, sizeof dis);
    dis[1][1][g[1][1]] = 0;
    q.push((Node){1, 1, g[1][1], 0});
    while(!q.empty()) {
        Node u = q.top(); q.pop();
        if(vis[u.x][u.y][u.s]) continue;
        if(u.x == n && u.y == m) return u.d;
        for (int i = 0; i < 4; i++) {
            int nx = u.x + dx[i], ny = u.y + dy[i];
            if(nx < 1 || nx > n || ny < 1 || ny > m || w[u.x][u.y][i] == INF) continue;
            if(w[u.x][u.y][i] && ((u.s >> w[u.x][u.y][i] & 1) == 0)) continue;
            int d = u.d + 1, s = u.s | g[nx][ny];
            if(d < dis[nx][ny][s]) {
                dis[nx][ny][s] = d;
                q.push((Node){nx, ny, s, d});
            }
        }
    }
    return -1;
}
int main() {
    scanf("%d%d%d%d", &n, &m, &P, &K);
    for (int i = 1, x1, y1, x2, y2, v; i <= K; i++) {
        scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &v);
        if(!v) v = INF;
        if(x1 > x2) swap(x1, x2), swap(y1, y2);
        if(y1 > y2) swap(x1, x2), swap(y1, y2);

        if(x1 < x2) {
            w[x1][y1][1] = v;
            w[x2][y2][0] = v;
        } else {
            w[x1][y1][3] = v;
            w[x2][y2][2] = v;
        }
    }
    scanf("%d", &S);
    for (int i = 1, x, y, v; i <= S; i++) {
        scanf("%d%d%d", &x, &y, &v);
        g[x][y] |= 1 << v;
    }
    printf("%d\n", dijkstra());
    return 0;
}

网络流 24 题

原文：https://www.cnblogs.com/dmoransky/p/12342004.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)