题解 AT1031 Reverse a Road II

zerc · 2022-09-23 08:47:52 · 题解

AT1031 Reverse a Road II Luogu | AtCoder

前置知识：P3376 【模板】网络最大流

因为每条边最多只能走一遍，所以建一条容量为 1 的边，跑一遍最大流。

考虑将 s 能扩展到的节点扔进 \text{set}_s，将能扩展到 t 的节点扔进 \text{set}_t，枚举残量网络上的边 e，如果 u \in \text{set}_t \land v \in \text{set}_s，那么反转这条边就能够构成一条 s \to t 的合法路径，累加 tot。

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

const int maxn = 2022;
const int maxm = 20222;

struct edge { int to, nxt, flow; }  e[maxm];
int cnt=1, head[maxn], dis[maxn], cur[maxn];
bool sets[maxn], sett[maxn];
int n, m, s, t, tot, ans;

void add(int u, int v, int w) {
    e[++cnt] = {v, head[u], w}; head[u] = cnt;
    e[++cnt] = {u, head[v], 0}; head[v] = cnt;
}

bool bfs(int s, int t) {
    memset(dis, 0, sizeof dis);
    memcpy(cur, head, sizeof head);
    int x;  queue<int> q;
    q.push (s); dis[s] = 1;
    while (!q.empty()) {
        x = q.front(); q.pop();
        for (int i = head[x]; i; i = e[i].nxt) {
            if (e[i].flow && !dis[e[i].to]) {
                dis[e[i].to] = dis[x] + 1;
                q.push(e[i].to);
                if (e[i].to == t) return 1;
            }
        }
    }
    return 0;
}

int dfs(int x, int flow) {
    if (x == t) return flow;
    int rest = flow; int i;
    for (i = cur[x]; i; i = e[i].nxt) {
        if (e[i].flow && dis[e[i].to] == dis[x] + 1) {
            int k = dfs(e[i].to, min(rest, (int)e[i].flow));
            if (!k) dis[e[i].to] = -1;
            e[ i ].flow -= k;
            e[i^1].flow += k;
            if (!(rest -= k)) break;
        }
    }
    cur[x] = i;
    return flow - rest;
}

int Dinic() {
    int maxflow = 0;
    while (bfs (s, t))
        maxflow += dfs(s, INT_MAX);
    return maxflow;
}

void calc() {
    queue<int> q;
    q.push(s); sets[s] = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].to;
            if (!sets[v] && e[i].flow) {
                sets[v] = 1, q.push(v);
            }
        }
    }
    q.push(t); sett[t] = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].to;
            if (!sett[v] && !e[i].flow) {
                sett[v] = 1, q.push(v);
            }
        }
    }
    for (int i = 2; i <= cnt; i += 2) {
        int u = e[i^1].to, v = e[i].to;
        if (e[i].flow && sets[v] && sett[u]) tot++;
    }
    if (tot) ans++;
}

void clear() {
    cnt = 1; ans = tot = 0;
    memset(head, 0, sizeof head);
    memset(sets, 0, sizeof sets);
    memset(sett, 0, sizeof sett);
}

int main() {
    while(1) {
        scanf("%d %d %d %d", &n, &m, &s, &t);
        if (!n && !m && !s && !t) return 0;
        clear();
        for (int i = 1; i <= m; i++) {
            int u, v; scanf("%d %d", &u, &v);
            add(u, v, 1);
        }
        ans = Dinic(), calc();
        printf("%d %d\n", ans, tot);
    }
}