FLOW1 - Giao lưu
Tác giả: hieult
Ngôn ngữ: C++
#include<cstdio>
#include<cmath>
#include<math.h>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<sstream>
#include<list>
#define fi first
#define se second
#define PB push_back
#define MP make_pair
#define ep 0.00001
#define oo 111111111
#define mod 1000000007
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
#define rep(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, x) memset(a, x, sizeof(a))
#define SZ(a) (int)(a.size())
//#define g 9.81
double const PI=4*atan(1.0);
using namespace std;
typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;
typedef long long ll;
// Dinic
void OPEN(){
freopen("A.in","r",stdin);
freopen("A.out","w",stdout);
}
#define maxn 1311
#define maxe (1 << 20)
struct Dinic{
int s, t, E, adj[maxe], cap[maxe], flow[maxe], next[maxe],
last[maxn], que[maxn], level[maxn], run[maxn];
void init(int _s, int _t){
s = _s; t = _t; E = 0;
memset(last, -1, sizeof(last));
}
void add(int u, int v, int c1, int c2){
adj[E] = v; cap[E] = c1; flow[E] = 0; next[E] = last[u]; last[u] = E++;
adj[E] = u; cap[E] = c2; flow[E] = 0; next[E] = last[v]; last[v] = E++;
}
bool bfs(){
memset(level, -1, sizeof(level));
level[s] = 0;
int size = 0; que[size++] = s;
rep(i, size){
for(int u = que[i], e = last[u]; e != -1; e = next[e]){
int v = adj[e];
if(level[v] == -1 && flow[e] < cap[e]){
level[v] = level[u] + 1;
que[size++] = v;
}
}
}
return level[t] != -1;
}
int dfs(int u, int bot){
if(u == t) return bot;
for(int &e = run[u]; e != -1; e = next[e]){
int v = adj[e], delta;
if(level[v] == level[u] + 1 && flow[e] < cap[e] && (delta = dfs(v, min(bot, cap[e] - flow[e]))) > 0){
flow[e] += delta;
flow[e ^ 1] -= delta;
return delta;
}
}
return 0;
}
ll maxflow(){
ll total = 0;
while(bfs()){
memcpy(run, last, sizeof(last));
for(int delta = dfs(s, oo); delta > 0; delta = dfs(s, oo)) total += delta;
}
return total;
}
}dinic;
int n, m, x;
char s[11111];
vector<pair<int, int> > V1[300], V2[300];
int main(){
//OPEN();
scanf("%d %d\n", &n, &m);
dinic.init(0, 2 * n + 2 * m + 1);
FOR(i, 1, m) dinic.add(n + i, n + m + i, 1, 0);
FOR(i, 1, n) dinic.add(0, i, 1, 0);
FOR(i, 1, n) dinic.add(n + m + m + i, n + n + m + m + 1, 1, 0);
FOR(i, 1, n){
gets(s);
istringstream iss(s);
while(iss >> x){
V1[x].PB(MP(dinic.E, i));
dinic.add(i, n + x, 1, 0);
}
}
FOR(i, 1, n){
gets(s);
istringstream iss(s);
while(iss >> x){
V2[x].PB(MP(dinic.E, i));
dinic.add(n + m + x, n + m + m + i, 1, 0);
}
}
// printf("%lld\n",dinic.maxflow());
dinic.maxflow();
FOR(i, 1, m){
int t1 = 0, t2 = 0;
rep(j, SZ(V1[i])) if(dinic.flow[V1[i][j].fi]) t1 = V1[i][j].se;
rep(j, SZ(V2[i])) if(dinic.flow[V2[i][j].fi]) t2 = V2[i][j].se;
printf("%d %d\n",t1,t2);
}
}