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