Pagini recente » Cod sursa (job #2815752) | Cod sursa (job #2686324) | Cod sursa (job #434709) | Cod sursa (job #2246634) | Cod sursa (job #2658671)
/*
`-/oo+/- ``
.oyhhhhhhyo.`od
+hhhhyyoooos. h/
+hhyso++oosy- /s
.yoooossyyo:``-y`
..----.` ``.-/+:.`
`````..-::/.
`..```.-::///`
`-.....--::::/:
`.......--::////:
`...`....---:::://:
`......``..--:::::///:`
`---.......--:::::////+/`
----------::::::/::///++:
----:---:::::///////////:`
.----::::::////////////:-`
`----::::::::::/::::::::-
`.-----:::::::::::::::-
...----:::::::::/:-`
`.---::/+osss+:`
``.:://///-.
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cmath>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugsp(x) cerr << #x << " " << x << " "
using namespace std;
const int INF = 2e9;
class Flow_Graph {
private:
int sz;
struct Edge {
int to, flow, cap, rev;
};
vector <vector <Edge>> adj;
vector <int> lev, rem;
public:
Flow_Graph(int n) {
sz = n;
adj.resize(5 + n);
lev.resize(5 + n);
rem.resize(5 + n);
}
void AddEdge(int from, int to, int cap) {
Edge x = {to, 0, cap, adj[to].size()};
Edge y = {from, 0, 0, adj[from].size()};
adj[from].push_back(x);
adj[to].push_back(y);
}
bool BFS() {
for(int i = 0; i <= sz; i++) lev[i] = 0;
lev[0] = 1;
queue <int> q;
q.push(0);
while(!q.empty()) {
int from = q.front();
q.pop();
for(int it = 0; it < adj[from].size(); it++) {
Edge e = adj[from][it];
if(!lev[e.to] && e.flow < e.cap) {
lev[e.to] = 1 + lev[from];
q.push(e.to);
}
}
}
return (lev[sz] > 0);
}
int DFS(int from, int flow) {
if(from == sz) return flow;
for(int &it = rem[from]; it < adj[from].size(); it++) {
Edge &e = adj[from][it];
if(lev[e.to] == 1 + lev[from] && e.flow < e.cap) {
int curr_flow = min(flow, e.cap - e.flow);
int temp_flow = DFS(e.to, curr_flow);
if(temp_flow) {
e.flow += temp_flow;
adj[e.to][e.rev].flow -= temp_flow;
return temp_flow;
}
}
}
return 0;
}
int MaxFlow() {
int ans(0);
while(BFS()) {
for(int i = 0; i <= sz; i++) rem[i] = 0;
int flow = DFS(0, INF);
while(flow) {
ans += flow;
flow = DFS(0, INF);
}
}
return ans;
}
void Construct_Edges(vector <pair <int, int>> &edges) {
int n = sz / 2;
for(int i = 1; i <= n; i++) {
for(auto it : adj[i]) {
if(it.flow > 0)
edges.push_back(make_pair(i, it.to - n));
}
}
}
void Print() {
for(int i = 0; i <= sz; i++) {
cerr << i << " ";
for(auto it : adj[i]) {
debugsp(it.to);
debug(it.flow);
//printf("%d ", it.to);
}
cerr << '\n';
}
}
};
vector <pair <int, int>> edges;
int main() {
freopen("harta.in", "r", stdin);
freopen("harta.out", "w", stdout);
int n, s, t;
scanf("%d", &n);
s = 0;
t = 1 + 2 * n;
Flow_Graph G(1 + 2 * n);
for(int i = 1; i <= n; i++) {
int x, y;
scanf("%d%d", &x, &y);
G.AddEdge(s, i, x);
G.AddEdge(n + i, t, y);
for(int j = n + 1; j <= 2 * n; j++) {
if(i + n != j) {
G.AddEdge(i, j, 1);
}
}
}
int mflow = G.MaxFlow();
G.Construct_Edges(edges);
printf("%d\n", edges.size());
for(pair <int, int> it : edges) {
printf("%d %d\n", it.first, it.second);
}
fclose(stdin);
fclose(stdout);
return 0;
}