結果
問題 | No.2914 正閉路検出 |
ユーザー |
|
提出日時 | 2024-10-04 22:53:59 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,193 bytes |
コンパイル時間 | 1,820 ms |
コンパイル使用メモリ | 188,436 KB |
実行使用メモリ | 32,772 KB |
最終ジャッジ日時 | 2024-10-04 22:54:13 |
合計ジャッジ時間 | 11,354 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 WA * 39 |
ソースコード
#include<bits/stdc++.h>using namespace std;using ll = long long;#define all(a) (a).begin(), (a).end()#define pb push_back#define fi first#define se secondmt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());const ll MOD1000000007 = 1000000007;const ll MOD998244353 = 998244353;const ll MOD[3] = {999727999, 1070777777, 1000000007};const ll LINF = 1LL << 60LL;const int IINF = (1 << 30) - 2;template<typename T>struct edge{int from;int to;T cost;int id;edge(){}edge(int to, T cost=1) : from(-1), to(to), cost(cost){}edge(int to, T cost, int id) : from(-1), to(to), cost(cost), id(id){}edge(int from, int to, T cost, int id) : from(from), to(to), cost(cost), id(id){}void reverse(){swap(from, to);}};template<typename T>struct edges : std::vector<edge<T>>{void sort(){std::sort((*this).begin(),(*this).end(),[](const edge<T>& a, const edge<T>& b){return a.cost < b.cost;});}};template<typename T = bool>struct graph : std::vector<edges<T>>{private:int n = 0;int m = 0;edges<T> es;bool dir;public:graph(int n, bool dir) : n(n), dir(dir){(*this).resize(n);}void add_edge(int from, int to, T cost=1){if(dir){es.push_back(edge<T>(from, to, cost, m));(*this)[from].push_back(edge<T>(from, to, cost, m++));}else{if(from > to) swap(from, to);es.push_back(edge<T>(from, to, cost, m));(*this)[from].push_back(edge<T>(from, to, cost, m));(*this)[to].push_back(edge<T>(to, from, cost, m++));}}int get_vnum(){return n;}int get_enum(){return m;}bool get_dir(){return dir;}edge<T> get_edge(int i){return es[i];}edges<T> get_edge_set(){return es;}};template<typename T>struct redge{int from, to;T cap, cost;int rev;redge(int to, T cap, T cost=(T)(1)) : from(-1), to(to), cap(cap), cost(cost){}redge(int to, T cap, T cost, int rev) : from(-1), to(to), cap(cap), cost(cost), rev(rev){}};template<typename T> using Edges = vector<edge<T>>;template<typename T> using weighted_graph = vector<Edges<T>>;template<typename T> using tree = vector<Edges<T>>;using unweighted_graph = vector<vector<int>>;template<typename T> using residual_graph = vector<vector<redge<T>>>;void solve(){int n, m; cin >> n >> m;graph<ll> G(n, true);vector<tuple<int, int, ll>> es(2*m);for(int i=0; i<m; i++){int u, v; cin >> u >> v;ll w; cin >> w;u--; v--;es[2*i] = {u, v, w};es[2*i+1] = {v, u, -w};G.add_edge(u, v, w);G.add_edge(v, u, -w);}vector<ll> dist(n, -LINF);vector<int> dep(n, 0);vector<int> epar(n, -1), vpar(n, -1);function<void(int, int)> dfs = [&](int v, int p){for(auto e : G[v]) if(e.to != p && dist[e.to] == -LINF){dist[e.to] = dist[v] + e.cost;dep[e.to] = dep[v] + 1;epar[e.to] = e.id;vpar[e.to] = v;dfs(e.to, v);}};for(int s=0; s<n; s++) if(dist[s]==-LINF){dist[s] = 0;dfs(s, -1);}for(int v=0; v<n; v++)for(auto e : G[v]){if(dist[e.from]-dist[e.to]+e.cost!=0 && dep[e.to] < dep[e.from]){vector<int> path;int a = e.to, b = e.from;path.pb(e.id);while(b != a){path.pb(epar[b]);b = vpar[b];}reverse(all(path));ll sum = 0;for(int i : path) sum += get<2>(es[i]);if(sum < 0) reverse(all(path));cout << (int)path.size() << '\n';cout << a+1 << '\n';for(auto i : path) cout << i/2+1 << ' ';cout << '\n';return;}}cout << -1 << '\n';}int main(){cin.tie(nullptr);ios::sync_with_stdio(false);int T=1;//cin >> T;while(T--) solve();}