Cod sursa(job #2960061)

Utilizator mihneagherghelMihnea Gherghel-Butan mihneagherghel Data 3 ianuarie 2023 15:14:02
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.63 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

int n, m, s, t, fluxMaxim; // s-nodul sursa, t-nodul destinatie din reatea asociata grafului 
vector<vector<int>> capacitate;
vector<vector<int>> rezultat;
vector<int> tata;
vector<vector<int>> listaAdiacenta;
vector<int> degreeIn, degreeOut;
ifstream fin("harta.in");
ofstream fout("harta.out");

void citire()
{
	fin >> n;
	degreeIn = vector<int>(n + 1, 0);
	degreeOut = vector<int>(n + 1, 0);
	listaAdiacenta = vector<vector<int>>(2*n+3, vector<int>());
	capacitate = vector<vector<int>>(2 * n + 3, vector<int>(2 * n + 3, 0));
	rezultat = vector<vector<int>>(n + 1, vector<int>());
	tata = vector<int>(2 * n + 2, -1);
	for (int i = 1; i <= n; i++)
	{
		fin >> degreeOut[i] >> degreeIn[i];
	}
}
// constructia retelei de transport 
void constructieRetea()
{
	s = 0; t = 2 * n + 1;
	// conectam toate nodurile din multimea X la sursa printr-o muchie cu capacitatea egala cu gradul exterior al fiecarui nod 
	for (int i = 1; i <= n; i++)
	{
		listaAdiacenta[s].push_back(i);
		listaAdiacenta[i].push_back(s);
		capacitate[s][i] = degreeOut[i];
	}
	// conectam toate nodurile din multimea Y la destinatie print-o muchie cu capacitatea egala cu gradul intern al fiecarui nod
	for (int i = n + 1; i < t; i++)
	{
		listaAdiacenta[t].push_back(i);
		listaAdiacenta[i].push_back(t);
		capacitate[i][t] = degreeIn[i-n];
	}
	// conectam toate nodurile din multimile X si Y print-o muchie cu capacitatea egala cu 1 mai putin nodurile care provin din acelasi nod
	for (int i = 1; i <= n; i++)
	{
		for (int j = n + 1; j < t; j++)
		{
			if (i + n == j)
				continue;
			listaAdiacenta[i].push_back(j);
			listaAdiacenta[j].push_back(i);
			capacitate[i][j] = 1;
		}
	}
}
// resetam vectorul de parinti
void reseteazaParinte()
{
	for (int i = 0; i <= t; i++)
	{
		tata[i] = -1;
	}
	tata[s] = -2;
}
// descoperirea unui lant nesaturat si calculam capacitatea reziduala minima a lantului
int bfs()
{
	queue<pair<int, int>> coada;
	coada.push({ s,10000000 });
	while (!coada.empty())
	{
		int nod = coada.front().first;
		int flux = coada.front().second;
		coada.pop();
		for (int i : listaAdiacenta[nod] )
		{
			if (tata[i] == -1 && capacitate[nod][i]>0)
			{
				tata[i] = nod;
				int flow = min(flux, capacitate[nod][i]);
				if (i == t)
				{
					return flow;
				}
				coada.push({ i,flow });
			}
		}
	}
	return 0;
}
void afisare()
{
	fout << fluxMaxim << "\n";
	for (int i = 1; i <= n; i++)
	{
		for (int j : rezultat[i])
		{
			fout << i << " " << j - n << "\n";
		}
	}
}
int main()
{
	citire();
	constructieRetea();
	reseteazaParinte();
	int c;
	// cat timp descoperim un lant nesaturat in reteua de transport
	while (c=bfs())
	{
		fluxMaxim = fluxMaxim + c;
		int nod = t;
		// revizuim fluxul de-a lungul lantului descoperit si adaugam sau scoatem din lista de adiacenta a grafului rezultat muchii
		while (nod != s)
		{
			int stramos = tata[nod];
			capacitate[stramos][nod] -= c;
			capacitate[nod][stramos] += c;
			if (nod > s && nod < t && stramos<t && stramos>s)
			{
				// adaugam muchia in graful rezultat daca este directa
				if (stramos < nod) 
				{
					rezultat[stramos].push_back(nod);
				}
				// scoatem muchia din graful rezultat daca este indirecta 
				else
				{
					for (int i = 0; i < rezultat[nod].size(); i++)
					{
						if (rezultat[nod][i] == stramos)
						{
							rezultat[nod].erase(rezultat[nod].begin() + i);
							break;
						}
					}
				}
			}
			nod = stramos;
		}
		reseteazaParinte();
	}
	afisare();
	//Compleixtate(n*m*m)
}