Cod sursa(job #3336940)

Utilizator uncrownedHojda Adelin uncrowned Data 26 ianuarie 2026 19:22:51
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.2 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("harta.in");
ofstream fout("harta.out");

#define cin fin
#define cout fout

vector<int> g[1001];
int c[1001][1001];
int flow[1001][1001];
int parent[1001];
int n, m;
bool v[1001];
bool bfs() {
	queue<int> q;
	q.push(1);
	memset(v,0,sizeof(v));
	v[1]=true;
	while(!q.empty()) {
		int node = q.front();
		q.pop();
		if (node==n) continue;
		for(auto i : g[node]) {
			if (flow[node][i]==c[node][i] || v[i]) continue;
			v[i]=true;
			q.push(i);
			parent[i]=node;
		}
	}
	return v[n];
}
int in[101];
int out[101];

int main()
{
	cin >> n;
    int nn=n;
	for(int i = 1;  i<= n; i++) {
		cin >> out[i] >> in[i];
	}
	for(int i = 1;  i<= n; i++) {
        int x = 1;
        int y = i+1;
        c[x][y] = out[i];
        g[x].push_back(y);
        g[y].push_back(x);
	}
	int t = 2*n+2;
	for(int i = 1; i <= n; i++) {
	    int x = i+1+n;
	    int y=t;
	    c[x][y]=in[i];
	    g[x].push_back(y);
	    g[y].push_back(x);
	}
	for(int i = 1; i <= n; i++) {
	    for(int j = 1; j <= n; j++) {
	        if (i==j)continue;
	        int x = i+1;
	        int y = j+1+n;
	        c[x][y]=1;
	        g[x].push_back(y);
	        g[y].push_back(x);
	    }
	}
	n = t;
	int maxflow=0;
	for(; bfs(); ) {
		for(auto node : g[n]) {
			if (flow[node][n]==c[node][n] || !v[node]) continue;
			parent[n]=node;
			int flowmin=INT_MAX;
			for(node=n; node != 1; node=parent[node]) {
				flowmin = min(flowmin, c[parent[node]][node]-flow[parent[node]][node]);
			}
			if (flowmin==0) continue;
			for(node=n; node != 1; node=parent[node]) {
				flow[parent[node]][node] += flowmin;
				flow[node][parent[node]] -= flowmin;
			}
			maxflow += flowmin;
		}
	}
	n=nn;
	vector<pair<int, int>> sol;
	int m=0;
    for(int i = 1; i <= n; i++) {
	    for(int j = 1; j <= n; j++) {
	        if (i==j)continue;
	        int x = i+1;
	        int y = j+1+n;
	        c[x][y]=1;
	        if (flow[x][y]==1) {
	            sol.push_back({i, j});
	            m++;
	        }
	    }
	}
    cout << m << "\n";
    for(int i = 0; i < m; i++) {
        cout << sol[i].first << " " << sol[i].second << "\n";
    }
	return 0;
}