Cod sursa(job #2962173)

Utilizator Cosmin3105Cosmin Colceru Cosmin3105 Data 7 ianuarie 2023 21:52:55
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

vector<vector<int>> la;

int n, nr, src, dest, nrDrumuri;
int cap[205][205];
bool vizitat[205];
int flux[205][205];
int tata[205];


int bfs() {
	queue<int> coada;

	for (int i = 0; i < nr; i++) {
		vizitat[i] = false;
	}

	vizitat[src] = true;
	coada.push(src);

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

		for (auto vecin : la[nod]) {
			if (!vizitat[vecin] && flux[nod][vecin] < cap[nod][vecin]) {
				vizitat[vecin] = true;
				tata[vecin] = nod;
				coada.push(vecin);

				if (vecin == dest)
					return 1;
			}
		}
	}
	return 0;
}

int fluxMinRamas(int nod) {
	if (nod == src)
		return INT32_MAX;

	int nodTata = tata[nod];
	int flx = cap[nodTata][nod] - flux[nodTata][nod];

	return min(flx, fluxMinRamas(nodTata));
}

void actualizareFlux(int nod) {
	if (nod == src)
		return;

	int nodTata = tata[nod];
	flux[nodTata][nod] += 1;
	flux[nod][nodTata] -= 1;

	actualizareFlux(nodTata);
}

int main() {
	fin >> n;

	nr = 2 * n + 2;
	src = 0;
	dest = nr - 1;

	la.resize(nr);

	for (int i = 1; i <= n; i++) {
		int x, y;
		fin >> x >> y;
		cap[src][i] = x;
		cap[i + n][dest] = y;
	}

	//formam muchiile
	for (int i = 1; i <= n; i++) {
		la[src].push_back(i);
		la[i].push_back(src);
	}

	for (int i = n + 1; i < nr - 1; i++) {
		la[i].push_back(dest);
		la[dest].push_back(i);
	}

	for (int i = 1; i <= n; i++) {
		for (int j = n + 1; j < nr - 1; j++) {
			if (j - i == n)
				continue;

			la[i].push_back(j);
			la[j].push_back(i);
			cap[i][j] = 1;
		}
	}

	while (bfs()) {
		for (auto vecin : la[dest]) {
			if (!vizitat[vecin] || fluxMinRamas(dest) == 0)
				continue;

			nrDrumuri++;

			actualizareFlux(dest);
		}
	}

	fout << nrDrumuri << endl;

	for (int i = 1; i <= n; i++) {
		for (int j = n + 1; j < nr; j++) {
			if (flux[i][j] == 1)
				fout << i << " " << j - n << endl;
		}
	}
}