LOJ#6000. 「网络流 24 题」搭配飞行员

发布于 18 天前  14 次阅读


Link

Sol

持续更新网络流24题

一个飞行员配一个副飞行员,就把飞行员和源点连一条容量为1的边,再往可以搭的副飞行员连一条容量为1的边,副飞行员和汇点连一条容量为1的边。跑最大流即可。

Code

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

const int SIZE = 2e2 + 5;
const int SIZE_M = 1e5 + 5;
const int s = 0;
const int inf = 0x7f7f7f7f;

int n, m, num = 1, maxFlow, t;
int head[SIZE], dep[SIZE], cur[SIZE], vis[SIZE];

struct node {
    int to, v, nxt;
} edge[SIZE_M << 1];

inline int read()
{
    char ch = getchar();
    int f = 1, x = 0;
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
    return x * f;
}

inline void addEdge(int u, int v, int d)
{
    edge[++ num].to = v, edge[num].v = d, edge[num].nxt = head[u];
    head[u] = num;
}

inline int bfs()
{
    std::queue < int > q;
    for (int i = 0; i <= n + 1; ++ i) dep[i] = inf;
    dep[s] = 0, cur[s] = head[s];
    q.push(s);
    while (!q.empty()) {
        int u = q.front(), v;
        q.pop();
        for (int i = head[u]; i; i = edge[i].nxt) {
            v = edge[i].to;
            if (dep[v] != inf || edge[i].v <= 0) continue;  
            dep[v] = dep[u] + 1, cur[v] = head[v];
            q.push(v);
            if (v == t) return 1;
        }
    }
    return 0;
}

inline int dinic(int u, int val)
{
    if (u == t) return val;
    int ans = 0, k = 0;
    for (int i = cur[u]; i && val; i = edge[i].nxt) {
        int v = edge[i].to; 
        cur[u] = i;
        if (edge[i].v > 0 && dep[v] == dep[u] + 1) {
            k = dinic(v, std::min(edge[i].v, val));
            if (!k) dep[v] = inf;
            edge[i].v -= k, edge[i ^ 1].v += k;
            ans += k, val -= k;
        }
    }
    // printf("u:%d ans:%d\n", u, ans);
    return ans;
}

int main()
{
    n = read(), m = read();
    int u, v;
    while (std::cin >> u >> v) {
        addEdge(u, v, 1); addEdge(v, u, 0);
    }
    t = n + 1;
    for (int i = 1; i <= n; ++ i) {
        if (i <= m) {
            addEdge(s, i, 1); addEdge(i, s, 0);
        }
        else {
            addEdge(i, t, 1); addEdge(t, i, 0);
        }
    }
    while (bfs()) maxFlow += dinic(s, inf);
    printf("%d\n", maxFlow);
    return 0;
}

因为这篇题解是补发的,所以代码比较远古了


学会生存 学会关心