HIWAY - Hai đường đi

Tác giả: ladpro98

Ngôn ngữ: C++

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <fstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define REP(i, a, b) for(int i = (a); i <=(b); ++i)
#define FORD(i, a, b) for(int i = (a); i > (b); --i)
#define REPD(i, a, b) for(int i = (a); i >=(b); --i)
#define TR(it, a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
#define RESET(a, v) memset(a, (v), sizeof(a))
#define SZ(a) (int(a.size()))
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>
#define VII vector<II>
#define endl '\n'

const int N = 111;
const int INF = INT_MAX;

using namespace std;

int T[N], d[N];
bool inQ[N], was[N];
int cost[N][N], cap[N][N], flow[N][N];
int n, m, source, sink, minCost, maxFlow;

bool findPath() {
  queue<int> Q;
  REP(i, 1, n) {
    T[i] = 0; d[i] = INF; inQ[i] = 0;
  }
  Q.push(source); d[source] = 0; inQ[source] = 1;
  while (!Q.empty()) {
    int u = Q.front(); Q.pop(); inQ[u] = 0;
    REP(v, 1, n)
    if (flow[u][v] < cap[u][v]) {
      int uv = cost[u][v] * (flow[u][v] < 0 ? -1 : 1);
      if (d[v] > d[u] + uv) {
        T[v] = u;
        d[v] = d[u] + uv;
        if (!inQ[v]) {
          inQ[v] = 1;
          Q.push(v);
        }
      }
    }
  }
  return d[sink] < INF;
}

void incFlow() {
  int delta = INF;
  for (int v = sink; v != source; v = T[v])
    delta = min(delta, flow[T[v]][v] < 0 ? -flow[T[v]][v] : (cap[T[v]][v] - flow[T[v]][v]));
  for (int v = sink; v != source; v = T[v])
    flow[T[v]][v] += delta, flow[v][T[v]] -= delta;
  maxFlow += delta;
  minCost += delta * d[sink];
}

VI path;

void showPath(int u) {
  path.PB(u);
  was[u] = 1;
  REP(v, 1, n)
  if (flow[u][v] > 0 && !was[v]) {
    showPath(v); break;
  }
}

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  #ifdef _LAD_
    freopen("HIWAY.in", "r", stdin);
  #endif // _LAD_
  cin >> n >> m >> source >> sink;
  int u, v;
  FOR(i, 0, m) {
    cin >> u >> v; cin >> cost[u][v];
    cost[v][u] = cost[u][v];
    cap[u][v] = cap[v][u] = 1;
  }
  ++n;
  cap[n][source] = 2;
  int S = source; source = n;
  while (findPath()) incFlow();
  if (maxFlow < 2) cout << -1 << endl;
  else {
    cout << minCost << endl;
    showPath(S);
    cout << SZ(path) << ' ';
    for (int it: path) cout << it << ' '; cout << endl;
    was[sink] = 0; path.clear();
    showPath(S);
    cout << SZ(path) << ' ';
    for (int it: path) cout << it << ' '; cout << endl;
  }
  return 0;
}

Download