Pagini recente » Cod sursa (job #2225322) | Cod sursa (job #621017) | Cod sursa (job #1422875) | Cod sursa (job #626765) | Cod sursa (job #2744275)
#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct flow {
const int INF = (int) 1e9;
struct edge {
int cap;
int to;
int nxt;
};
int n;
vector<int> pos;
vector<int> level;
vector<int> head;
vector<edge> edges;
void init(int nn) {
n = nn;
pos.clear();
level.clear();
edges.clear();
head.clear();
head.resize(n + 1, -1);
pos.resize(n + 1);
level.resize(n + 1);
}
void add(int a, int b, int c) {
edges.push_back({c, b, head[a]});
edges.push_back({0, a, head[b]});
head[a] = (int) edges.size() - 2;
head[b] = (int) edges.size() - 1;
}
int dfs(int a, int cap) {
if (!cap || a == n) {
return cap;
}
while (pos[a] != -1) {
int i = pos[a];
pos[a] = edges[i].nxt;
if (edges[i].cap > 0 && level[edges[i].to] == 1 + level[a]) {
int x = dfs(edges[i].to, min(cap, edges[i].cap));
if (x > 0) {
edges[i].cap -= x;
edges[i ^ 1].cap += x;
return x;
}
}
}
return 0;
}
int get() {
int sol = 0;
while (1) {
for (int i = 1; i <= n; i++) {
level[i] = -1;
pos[i] = head[i];
}
level[1] = 0;
queue<int> q;
q.push(1);
while (!q.empty()) {
int a = q.front();
q.pop();
int ind = head[a];
while (ind != -1) {
int b = edges[ind].to;
if (edges[ind].cap > 0 && level[b] == -1) {
level[b] = 1 + level[a];
q.push(b);
}
ind = edges[ind].nxt;
}
}
if (level[n] == -1) {
break;
}
while (1) {
int x = dfs(1, INF);
if (x == 0) {
break;
}
sol += x;
}
}
return sol;
}
};
int main() {
freopen ("cuplaj.in", "r", stdin);
freopen ("cuplaj.out", "w", stdout);
int n, m, q;
scanf("%d %d %d", &n, &m, &q);
flow f;
f.init(1 + n + m + 1);
for (int i = 1; i <= n; i++) {
f.add(1, 1 + i, 1);
}
for (int i = 1; i <= m; i++) {
f.add(1 + n + i, 1 + n + m + 1, 1);
}
while (q--) {
int a, b;
scanf("%d %d", &a, &b);
f.add(1 + a, 1 + n + b, 1);
}
printf("%d\n", f.get());
for (int i = 1; i <= n; i++) {
int ind = f.head[1 + i];
while (ind != -1) {
int j = f.edges[ind].to - 1 - n;
if (1 <= j && j <= m && f.edges[ind].cap == 0) {
printf("%d %d\n", i, j);
}
ind = f.edges[ind].nxt;
}
}
return 0;
}