TIOJ 2117：殿壬與最大流

TIOJ 2117：殿壬與最大流

題目大意：有一張無向連通圖，$q$ 筆詢問，每筆詢問回答源點當 $s$，匯點當 $t$ 的最大流。喔對了，它有 $n$ 點 $n$ 邊。

解法：其實這題不須用到任何網路流的算法，因為可以知道這張圖會有一個環，剩下的都是樹邊，如果兩個點都在環上，最大流就是 $2$，否則就是 $1$。只是有一個 $\text{case}$ 是環的大小為 $2$，這時搭配一個 $\text{map}$ 判斷，就可以順利拿到 $\text{BottomCoder}$ 了！

$\text{Code：}$

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 2e5 + 5;

int n, q;
vector<int> adj[SIZE], st;
bool vs[SIZE], isc[SIZE];
map<pair<int, int>, int> cnt;

void dfs (int pos, int fa) {
    vs[pos] = 1;
    st.pb (pos);
    for (int np : adj[pos]) {
        if (np == fa) continue;
        if (vs[np]) {
            if (!isc[np]) {
                for (int i = st.size() - 1; i >= 0 && st[i] != np; i--) isc[st[i]] = 1;
                isc[np] = 1;
            }
        } else {
            dfs (np, pos);
        }
    }
    st.pop_back();
}

void solve() {
    cin >> n;
    FOR (i, 1, n) {
        int a, b;
        cin >> a >> b;
        adj[a].pb (b);
        adj[b].pb (a);
        cnt[{min (a, b), max(a, b)}]++;
    }
    bool two = 0;
    for (auto [p, c] : cnt) {
        if (c == 2) {
            two = isc[p.F] = isc[p.S] = 1;
            break;
        }
    }
    if (!two) dfs (1, 1);
    cin >> q;
    while (q--) {
        int a, b;
        cin >> a >> b;
        cout << 1 + (isc[a] & isc[b]) << '\n';
    }
}

int main() {
    Waimai;
    solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！