TIOJ 2254：D. 汽車不再繞圈圈

TIOJ 2254：D. 汽車不再繞圈圈

題目大意：一張 $n$ 點 $m$ 邊的有向圖，每個點有一個權重，可以想一個數字，只要權重小於我們想的數字的邊，就可以改變它的方向，目的是要讓這張圖變成一張有向無環圖。問數字最小可以是多少。

解法：首先可以知道要用二分搜，然後先把權重小於我們想的數字的邊隱藏，對整張圖拓樸排序一次，如果是有向無環圖，就可以按照拓樸排序的順序將邊定向。

$\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 = 1e5 + 5;

int n, m;
vector<int> adj[SIZE], lis (1, 0);
tuple<int, int, int> e[SIZE];

queue<int> q;
int deg[SIZE], to[SIZE];
vector<int> topo, ans;

bool ok (int x) {
    fill (deg, deg + n + 1, 0);
    FOR (i, 1, m) {
        auto [a, b, c] = e[i];
        if (c > x) {
            deg[b]++;
        }
    }
    FOR (i, 1, n) {
        if (deg[i] == 0) {
            q.push (i);
        }
    }
    topo.clear();
    while (!q.empty()) {
        int pos = q.front();
        q.pop();
        topo.pb (pos);
        for (int id : adj[pos]) {
            auto [a, np, c] = e[id];
            if (c <= x || pos == np) {
                continue;
            }
            deg[np]--;
            if (deg[np] == 0) {
                q.push (np);
            }
        }
    }
    return topo.size() == n;
}

void solve() {
    cin >> n >> m;
    FOR (i, 1, m) {
        int a, b, c;
        cin >> a >> b >> c;
        e[i] = {a, b, c};
        adj[a].pb (i);
        adj[b].pb (i);
        lis.pb (c);
    }
    sort (lis.begin(), lis.end());
    lis.erase (unique (lis.begin(), lis.end()), lis.end());
    int l = 0, r = lis.size() - 1;
    while (l < r) {
        int mid = (l + r) / 2;
        if (ok (lis[mid])) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    ok (lis[l]);
    FOR (i, 1, n) to[topo[i - 1]] = i;
    FOR (i, 1, m) {
        auto [a, b, c] = e[i];
        if (c <= lis[l] && to[a] > to[b]) {
            ans.pb (i);
        }
    }
    cout << lis[l] << ' ' << ans.size() << '\n';
    for (int x : ans) {
        cout << x << '\n';
    }
}

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

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