結果

問題 No.2914 正閉路検出
ユーザー tassei903
提出日時 2024-10-04 22:07:29
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,936 bytes
コンパイル時間 2,969 ms
コンパイル使用メモリ 128,392 KB
実行使用メモリ 814,568 KB
最終ジャッジ日時 2024-10-04 22:07:44
合計ジャッジ時間 9,812 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10 WA * 13 MLE * 1 -- * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
using namespace std;

using ll = long long;

struct Edge {
    int to, idx, weight;
};

tuple<int, int, int, vector<int>, vector<int>> find_cycle2(int N, int M, vector<vector<Edge>>& G) {
    vector<int> vis(N, 0), used(M, 0), par_v(N, -1), par_e(N, -1);
    vector<ll> potential(N, 0);

    for (int s = 0; s < N; ++s) {
        if (vis[s]) continue;
        vector<tuple<int, int, int, ll>> stack = {{s, -1, -1, 0}};
        
        while (!stack.empty()) {
            auto [v, p, e, pot] = stack.back(); stack.pop_back();
            if (e != -1 && used[e]) continue;
            if (vis[v] && pot != potential[v]) {
                par_v[v] = p;
                if (e != -1) par_e[v] = e;
                return {v, p, e, par_v, par_e};
            }
            vis[v] = 1;
            potential[v] = pot;
            if (e != -1) {
                par_e[v] = e;
                used[e] = 1;
            }
            par_v[v] = p;
            for (const auto& [a, ne, w] : G[v]) {
                if (used[ne]) continue;
                stack.emplace_back(a, v, ne, pot + w);
            }
        }
    }

    return {-1, -1, -1, par_v, par_e};
}

pair<vector<int>, vector<int>> cycle_detection2(int N, int M, vector<vector<Edge>>& G) {
    auto [v, p, e, par_v, par_e] = find_cycle2(N, M, G);
    
    if (p == -1) {
        return {{}, {}};
    } else {
        vector<int> cycle_v = {p};
        vector<int> cycle_e = {e};
        while (v != p) {
            e = par_e[p];
            p = par_v[p];
            cycle_v.push_back(p);
            cycle_e.push_back(e);
        }
        reverse(cycle_v.begin(), cycle_v.end());
        reverse(cycle_e.begin(), cycle_e.end());
        return {cycle_v, cycle_e};
    }
}

int32_t main() {
    int n, m;
    cin >> n >> m;

    vector<vector<Edge>> g(n);
    vector<tuple<int, int, int>> E;

    for (int i = 0; i < m; ++i) {
        int a, b, w;
        cin >> a >> b >> w;
        --a; --b;
        g[a].push_back({b, i, w});
        g[b].push_back({a, i, -w});
        E.emplace_back(a, b, w);
    }

    auto [cycle_v, cycle_e] = cycle_detection2(n, m, g);

    if (cycle_v.empty()) {
        cout << -1 << endl;
    } else {
        cout << cycle_v.size() << endl;
        ll ans = 0;
        int c = 0;
        for (int i : cycle_e) {
            if (get<0>(E[i]) == c) {
                ans += get<2>(E[i]);
                c = get<1>(E[i]);
            } else {
                ans -= get<2>(E[i]);
                c = get<0>(E[i]);
            }
        }
        if (ans > 0) {
            cout << cycle_v[0] + 1 << endl;
            for (int i : cycle_e) cout << i + 1 << " ";
        } else {
            cout << cycle_v[0] + 1 << endl;
            for (auto it = cycle_e.rbegin(); it != cycle_e.rend(); ++it) cout << *it + 1 << " ";
        }
        cout << endl;
    }

    return 0;
}
0