Cod sursa(job #2955309)

Utilizator Rares_StefanoiuRares Stefanoiu Rares_Stefanoiu Data 16 decembrie 2022 18:41:29
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.64 kb


#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;

int root, dest, n, m, d1, d2, c, total, l, r;

int tati[202];
vector<vector<int>>lista;
int flux[202][202];
int label[202];

ifstream f("harta.in");
ofstream g("harta.out");

bool BFS() {
	queue<int>q;
	for (int i = 0; i <= 2*n+1; i++)
	{
		tati[i] = -1;
		label[i] = 0;
	}
	label[0] = 1;
	q.push(0);
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (auto el : lista[x]) {
			if (label[el] == 0 && flux[x][el] > 0) {
				tati[el] = x;
				q.push(el);
				label[el] = 1;
				if (el == 2*n+1) {
					return 1;
				}
			}
		}
	}
	return 0;

}

int main() {
	f >> n;
	lista.resize(2*n + 2);
	for (int i = 1; i <= n; i++)
	{
		f >> d1 >> d2;
		flux[0][i] = d1;
		flux[n+i][2*n + 1] = d2;

		lista[0].push_back(i);
		lista[i].push_back(0);

		lista[n + i].push_back(2 * n + 1);
		lista[2 * n + 1].push_back(n + i);

		for (int j = n + 1; j <= 2 * n; j++)
		{
			if (j - i == n)
				continue;
			lista[i].push_back(j);
			lista[j].push_back(i);
			flux[i][j] = 1;
		}
	}
	while (BFS()) {
		for (auto el : lista[n])
		{
			if (!label[el])
				continue;
			int min1 = 10000000;
			int v = 2*n+1;
			while (v != 0)
			{
				min1 = min(min1, flux[tati[v]][v]);
				v = tati[v];
			}
			v = 2*n+1;
			while (v != 0) {
				flux[tati[v]][v] -= min1;
				flux[v][tati[v]] += min1;
				v = tati[v];
			}
			total = total + min1;
		}

	}
	g << total << "\n";
	for(int i=1;i<=n;i++)
		for(int j=n+1;j<=2*n+1;j++)
			if (flux[j][i] == 1) {
				g << i << " " << j - n << "\n";
				continue;
			}

}