KWAY - Trao đổi thông tin
Tác giả: happyboy99x
Ngôn ngữ: C++
#include<bits/stdc++.h>
using namespace std;
#define TR(v,i) for(__typeof((v).begin())i=(v).begin();i!=(v).end();++i)
const int N = 100, INF = 1e9;
vector<pair<int, int> > g[N+2];
vector<int> c, cost, f;
int n, m, k, s, t;
void addEdge(int u, int v, int cst, int lim) {
g[u].push_back(make_pair(v, c.size()));
g[v].push_back(make_pair(u, c.size()+1));
c.push_back(lim); c.push_back(0);
cost.push_back(cst); cost.push_back(-cst);
f.push_back(0); f.push_back(0);
}
pair<int, int> mincost(int s, int t, int n) {
int totalcost = 0, maxf = 0;
while(true) {
vector<int> d (n, INF);
vector<pair<int, int> > tr (n, make_pair(INF, INF));
vector<bool> inq (n, false);
queue<int> q;
d[s] = 0; q.push(s); inq[s] = true; tr[s] = make_pair(-1, -1);
while(!q.empty()) {
int u = q.front(); q.pop(); inq[u] = false;
TR(g[u], it) {
int v = it->first, e = it->second;
if(c[e] > f[e] && d[v] > d[u] + cost[e]) {
d[v] = d[u] + cost[e];
tr[v] = make_pair(u, e);
if(!inq[v]) q.push(v), inq[v] = true;
}
}
}
if(d[t] == INF) break;
int delta = INF;
for(int u = tr[t].first, v = t; u != -1; v = u, u = tr[u].first)
delta = min(delta, c[tr[v].second] - f[tr[v].second]);
for(int u = tr[t].first, v = t; u != -1; v = u, u = tr[u].first) {
f[tr[v].second] += delta;
f[tr[v].second ^ 1] -= delta;
}
maxf += delta; totalcost += d[t] * delta;
}
return make_pair(maxf, totalcost);
}
void dfs(int s, int t, vector<int> &v, vector<bool> &used) {
v.push_back(s);
if(s == t) {
cout << v.size();
TR(v, i) cout << ' ' << *i+1;
cout << '\n';
} else {
TR(g[s], it) {
int u = it->first, e = it->second;
if(!used[e] && c[e] == 1 && c[e] == f[e]) {
used[e] = true;
dfs(u, t, v, used);
break;
}
}
}
v.pop_back();
}
void printRemain() {
for(int u = 0; u < n; ++u) {
TR(g[u], it) {
int v = it->first, e = it->second;
if(c[e] == 1 && f[e] == 1)
cerr << "Remain " << u+1 << ' ' << v+1 << endl;
}
}
}
void enter() {
cin >> n >> m >> k >> s >> t; --s; --t;
for(int i = 0; i < m; ++i) {
int u, v, c; cin >> u >> v >> c; --u; --v;
addEdge(u, v, c, 1);
addEdge(v, u, c, 1);
}
addEdge(n, s, 0, k);
addEdge(t, n+1, 0, k);
}
int main() {
ios::sync_with_stdio(false);
enter();
pair<int, int> res = mincost(n, n+1, n+2);
if(res.first < k) cout << -1 << '\n';
else {
cout << res.second << '\n';
vector<int> tmp;
vector<bool> used (c.size(), false);
for(int i = 0; i < k; ++i) dfs(s, t, tmp, used);
}
return 0;
}