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

Download