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;
}