Cod sursa(job #2658669)

Utilizator MatteoalexandruMatteo Verzotti Matteoalexandru Data 14 octombrie 2020 18:23:48
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.73 kb
/*
                `-/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;
}