Cod sursa(job #2917121)

Utilizator lolismekAlex Jerpelea lolismek Data 3 august 2022 13:25:05
Problema Taramul Nicaieri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.76 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int N = 210, inf = 1e9;
int in[N + 1], out[N + 1];

int f[N + 1][N + 1], parent[N + 1], S, D, n, m;
bool viz[N + 1];

vector <int> adj[N + 1];

bool BFS(){
	for(int i = 0; i <= 2 * n + 1; i++)
		parent[i] = viz[i] = 0;

	queue <int> Q;

	Q.push(S);
	viz[S] = true;

	while(!Q.empty()){
		int nod = Q.front();
		Q.pop();

		if(nod == D)
			return true;

		for(auto vec : adj[nod]){
			if(!viz[vec] && f[nod][vec] > 0)
				parent[vec] = nod, viz[vec] = true, Q.push(vec);
		}
	}

	return false;
}

int main(){

	fin >> n;

	for(int i = 1; i <= n; i++)
		fin >> out[i] >> in[i], m += in[i];

	S = 0, D = 2 * n + 1;

	for(int i = 1; i <= n; i++){
		adj[S].push_back(i);
		adj[i].push_back(S);
		f[S][i] = in[i];
	}

	for(int i = 1; i <= n; i++)
		for(int j = n + 1; j <= 2 * n; j++){
			if(j != i + n){
				adj[i].push_back(j);
				adj[j].push_back(i);
				f[i][j] = 1;
			}
		}	

	for(int i = n + 1; i <= 2 * n; i++){
		adj[i].push_back(D);
		adj[D].push_back(i);
		f[i][D] = out[i - n];
	}

	while(BFS()){
		for(auto vec : adj[D]){
			if(f[vec][D] <= 0 || !viz[vec])
				continue;

			parent[D] = vec;

			int mini = inf, nod = D;
			while(nod != S)
				mini = min(mini, f[parent[nod]][nod]), nod = parent[nod];

			if(mini == 0)
				continue;

			nod = D;

			while(nod != S)
				f[parent[nod]][nod] -= mini, f[nod][parent[nod]] += mini, nod = parent[nod];
		}
	}

	fout << m << '\n';

	for(int i = 1; i <= n; i++)
		for(int j = n + 1; j <= 2 * n; j++)
			if(f[i][j] == 0 && f[j][i] != 0)
				fout << i << ' ' << j - n << '\n';

	return 0;
}