fork download
copy 
  1. #include <bits/stdc++.h> // NeOWami
  2. using namespace std;
  3.  
  4. #define ft first
  5. #define sc second
  6. #define int long long
  7. using pii = pair<int, int>;
  8. template<class T> using heapmin = priority_queue<T, vector<T>, greater<T>>;
  9. bool ckmin(int &u, int v) {
  10.     if (u > v) return u = v, 1;
  11.     return 0;
  12. }
  13. const int N = 2e5 + 5;
  14. const int inf = 1e18;
  15. int n, m, originS, originT, s, t, max_flow = 0;
  16. struct edge{
  17.     int u, v, c, f, cost;
  18. };
  19. vector<int> D[N];
  20. vector<edge> E;
  21. void add_edge(int u, int v, int cap, int cost) {
  22.     D[u].push_back(E.size()); E.push_back({u, v, cap, 0, cost});
  23.     D[v].push_back(E.size()); E.push_back({v, u, 0, 0, -cost});
  24. }
  25.  
  26. int dist[N], del[N], trace[N], cur_edge[N];
  27. int min_cost;
  28. int calc(int id) {
  29.     return E[id].cost + del[E[id].u] - del[E[id].v];
  30. }
  31. bool dijkstra() {
  32.     fill(dist + 1, dist + n + 1, inf);
  33.     fill(trace + 1, trace + n + 1, 0);
  34.  
  35.     heapmin<pii> Q;
  36.     dist[s] = 0;
  37.     Q.push({dist[s], s});
  38.  
  39.     while (!Q.empty()) {
  40.         int old = Q.top().ft, u = Q.top().sc;
  41.         Q.pop();
  42.         if (old != dist[u]) continue;
  43.         for (int id: D[u]) {
  44.             int v = E[id].v;
  45.             if (E[id].c > E[id].f && ckmin(dist[v], dist[u] + calc(id))) {
  46.                 trace[v] = u;
  47.                 Q.push({dist[v], v});
  48.             }
  49.         }
  50.     }
  51.     return dist[t] < inf;
  52. }
  53.  
  54. int dfs(int u, int val) {
  55.     if (u == t) return val;
  56.     for (int &i = cur_edge[u]; i < D[u].size(); i++) {
  57.         int id = D[u][i];
  58.         int v = E[id].v;
  59.         if (trace[v] == u && E[id].c > E[id].f && dist[v] == dist[u] + calc(id)) {
  60.             int flow = dfs(v, min(val, E[id].c - E[id].f));
  61.             if (flow) {
  62.                 E[id].f += flow;
  63.                 E[id ^ 1].f -= flow;
  64.                 min_cost += flow * E[id].cost;
  65.                 return flow;
  66.             }            
  67.         }
  68.     }
  69.     return 0;
  70. }
  71.  
  72. bool vis[N * 10];
  73. vector<pii> G[N];
  74. void Find_Path(int u , int p){
  75.     cout << u << " ";
  76.     for (pii item: G[u]) {
  77.         int id = item.ft, v = item.sc;
  78.         if(vis[id] || v == p) continue; 
  79.         vis[id] = 1; 
  80.         Find_Path(v, u); 
  81.     }
  82. }
  83. signed main() {
  84.     cin.tie(NULL)->sync_with_stdio(false);
  85.     if(ifstream("WALK.inp")) {
  86.         freopen("WALK.inp", "r", stdin);
  87.         freopen("WALK.out", "w", stdout);
  88.     }
  89.     cin >> n >> m;
  90.     for (int i = 1; i <= m; i++) {
  91.         int u, v, cost; cin >> u >> v >> cost;
  92.         add_edge(u, v, 1, cost);
  93.         add_edge(v, u, 1, cost);
  94.     }
  95.     originS = 1, originT = n;
  96.     n += 2;
  97.     s = n - 1; t = n;
  98.     add_edge(s, originS, 2, 0);
  99.     add_edge(originT, t, 2, 0);
  100.     while(dijkstra()) {
  101.         fill(cur_edge + 1, cur_edge + n + 1, 0);
  102.         for (int val = dfs(s, inf); val; val = dfs(s, inf)) max_flow += val;
  103.         for(int u = 1; u <= n; u++) if (dist[u] < inf) del[u] += dist[u];
  104.     }
  105.     if (max_flow != 2) return cout << -1, 0;
  106.  
  107.     cout << min_cost << "\n";
  108.  
  109.     for (int i = 0; i < E.size(); i += 2) if (E[i].u != s && E[i].v != t) {
  110.         if (E[i].f > 0 && E[i].cost > 0) {
  111.             int u = E[i].u, v = E[i].v;
  112.             G[u].push_back({i, v});
  113.             G[v].push_back({i, u});
  114.         }
  115.     }
  116.     Find_Path(1, 0);
  117.     return 0;
  118. }
  119.  
Success #stdin #stdout 0.01s 17048KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/VqYYOf
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!