KWAY - Trao đổi thông tin
Tác giả: flashmt
Ngôn ngữ: C++
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int oo = 1000111222;
vector <int> path;
struct edge
{
int x, y, cap, flow, cost;
};
struct MinCostMaxFlow
{
int n, S, T;
vector < vector <int> > a;
vector <int> dist, prev, done, pot;
vector <edge> e;
MinCostMaxFlow() {}
MinCostMaxFlow(int _n, int _S, int _T)
{
n = _n; S = _S; T = _T;
a = vector < vector <int> >(n + 1);
dist = vector <int>(n + 1);
prev = vector <int>(n + 1);
done = vector <int>(n + 1);
pot = vector <int>(n + 1, 0);
}
void addEdge(int x, int y, int _cap, int _cost)
{
edge e1 = {x, y, _cap, 0, _cost};
edge e2 = {y, x, 0, 0, -_cost};
a[x].push_back(e.size()); e.push_back(e1);
a[y].push_back(e.size()); e.push_back(e2);
}
pair <int,int> dijkstra()
{
int flow = 0, cost = 0;
for (int i = 1; i <= n; i++) done[i] = 0, dist[i] = oo;
priority_queue < pair<int,int> > q;
dist[S] = 0; prev[S] = -1;
q.push(make_pair(0, S));
while (!q.empty())
{
int x = q.top().second; q.pop();
if (done[x]) continue;
done[x] = 1;
for (int i = 0; i < int(a[x].size()); i++)
{
int id = a[x][i], y = e[id].y;
if (e[id].flow < e[id].cap)
{
int D = dist[x] + e[id].cost + pot[x] - pot[y];
if (!done[y] && D < dist[y])
{
dist[y] = D; prev[y] = id;
q.push(make_pair(-dist[y], y));
}
}
}
}
for (int i = 1; i <= n; i++) pot[i] += dist[i];
if (done[T])
{
flow = oo;
for (int id = prev[T]; id >= 0; id = prev[e[id].x])
flow = min(flow, e[id].cap - e[id].flow);
for (int id = prev[T]; id >= 0; id = prev[e[id].x])
{
cost += e[id].cost * flow;
e[id].flow += flow;
e[id ^ 1].flow -= flow;
}
}
return make_pair(flow, cost);
}
pair <int,int> minCostMaxFlow()
{
int totalFlow = 0, totalCost = 0;
while (1)
{
pair <int,int> u = dijkstra();
if (!done[T]) break;
totalFlow += u.first; totalCost += u.second;
}
return make_pair(totalFlow, totalCost);
}
void trace(int x)
{
if (x == T)
{
cout << path.size();
for (int i = 0; i < int(path.size()); i++) cout << ' ' << path[i];
puts("");
return;
}
path.push_back(x);
for (int i = 0; i < int(a[x].size()); i++)
{
int id = a[x][i];
if (e[id].flow > 0)
{
if (e[id].y < T) e[id].flow = 0;
trace(e[id].y);
return;
}
}
}
};
int main()
{
int n, m, F, s, t, x, y, z;
cin >> n >> m >> F >> s >> t;
int S = n + 1, T = n + 2;
MinCostMaxFlow u(T, S, T);
while (m--) cin >> x >> y >> z, u.addEdge(x, y, 1, z), u.addEdge(y, x, 1, z);
u.addEdge(S, s, F, 0);
u.addEdge(t, T, F, 0);
pair <int,int> ans = u.minCostMaxFlow();
if (ans.first < F) puts("-1");
else
{
cout << ans.second << endl;
while (F--) path.clear(), u.trace(s);
}
}