FLOW1 - Giao lưu

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 = 255, INF = 1e9;
vector<pair<int, int> > g[4*N+2];
vector<int> c, f;
pair<int, int> res[N];
int n, m;

void addEdge(int u, int v, 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);
	f.push_back(0); f.push_back(0);
}

void enter() {
	cin >> n >> m;
	for(int i = 0; i < m; ++i) addEdge(i, m+i, 1);
	string s; getline(cin, s);
	for(int i = 0; i < n; ++i) {
		getline(cin, s);
		stringstream inp (s);
		for(int x; inp >> x; --x, addEdge(2*m+i, x, 1));
		addEdge(2*(m+n), 2*m+i, 1);
	}
	for(int i = 0; i < n; ++i) {
		getline(cin, s);
		stringstream inp (s);
		for(int x; inp >> x; --x, addEdge(m+x, 2*m+n+i, 1));
		addEdge(2*m+n+i, 2*(m+n)+1, 1);
	}
}

void maxflow(int s, int t, int n) {
	while(true) {
		vector<pair<int, int> > tr (n, make_pair(INF, INF));
		tr[s] = make_pair(-1, -1);
		queue<int> q; q.push(s);
		while(!q.empty()) {
			int u = q.front(); q.pop();
			if(u == t) break;
			TR(g[u], it) {
				int v = it->first, e = it->second;
				if(c[e] - f[e] > 0 && tr[v].first == INF)
					tr[v] = make_pair(u, e), q.push(v);
			}
		}
		if(tr[t].first == 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;
		}
	}
}

void trace() {
	fill(res, res+m, make_pair(-1, -1));
	for(int i = 0; i < m; ++i) TR(g[i], it) {
		int v = it->first, e = it->second;
		if(f[e] == -1) TR(g[m+i], it) {
			int v2 = it->first, e2 = it->second;
			if(f[e2] == 1) res[i] = make_pair((v-2*m)%n, (v2-2*m)%n);
		}
	}
	for(int i = 0; i < m; ++i)
		cout << res[i].first + 1 << ' ' << res[i].second + 1 << '\n';
}

int main() {
	ios::sync_with_stdio(false);
	enter();
	maxflow(2*(m+n), 2*(m+n)+1, 2*(m+n+1));
	trace();
	return 0;
}

Download