Cod sursa(job #2962380)

Utilizator horiacoolNedelcu Horia Alexandru horiacool Data 8 ianuarie 2023 14:45:28
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.38 kb
// O posibila solutie pentru problema este sa cream
// un graf bipartit in care submultimile disjuncte (stanga si dreapta)
// sunt copie a multimii nodurilor grafului initial. Ducem muchii de cost 1
// pentru fiecare nod din stanga la fiecare nod din dreapta, exceptie
// facand el insusi. Adaugam acestui graf o sursa si o destinatie. Aduagam
// muchii de la sursa la fiecare nod din stanga de cost egal cu out_degree-ul
// nodului respectiv. Ducem muchii de la nodurile din dreapta la nodul
// destinatie de cost in_degree-ul nodului respectiv. Problema se reduce
// astfel la a gasi fluxul maxim in reteau creata. Muchiile prin care intra flux
// reprezinta o posibila solutie pentru gradele grafului date initial.
// Complexitate: complexitatea algoritmului de flux pe graful creat G(V, E)
// |V| = 2*N + 2	|E| = 2*N + N*(N-1) => O(|V|*|E|^2) = O(N*N^2^2) = O(N^5)
// Complexitatea este teoretica, solutia este mult mai buna in practica, motiv
// pentru care vedem limita N <= 100.
// 
// O solutie greedy mai buna decat cea a fluxului este prezentata mai jos: O(N^3)

#include <fstream>
#include <string.h>

using namespace std;

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

#define N_MAX 101

int N, M;
int out_degree[N_MAX], in_degree[N_MAX];

// degree_sizes[i] = numarul de noduri care inca au in_degree-ul `i`
// degree_list[i][j] = indexul celui de al `j`-lea nod care inca are in_degree-ul `i`
int degree_sizes[N_MAX], degree_list[N_MAX][N_MAX];

int main() {
	
	fin >> N;
	
	for (int i = 1; i <= N; ++i) {
		fin >> out_degree[i] >> in_degree[i];
		M += out_degree[i];
	}

	fout << M << '\n';

	for (int node = 1; node <= N; ++node) {
		memset(degree_sizes, 0, sizeof(degree_sizes));

		for(int i = 1; i <= N; ++i) {
			// mai putem duce muchii din `node` in `i`
			if (in_degree[i] != 0  && i != node) {
				// adugam nodul `i` la lista nodurilor care au in_degree-ul `in_degree[i]`
				degree_list[ in_degree[i] ][ ++degree_sizes[in_degree[i]] ] = i;
			}
		}

		// incercam sa ducem muchie catre nodurile care au in_degree-ul maxim
		for(int degree = N; degree > 0 && out_degree[node] > 0; --degree) {
			// iteram prin lista de noduri cu in_degree-ul `degree`
			for(int k = degree_sizes[degree]; k > 0 && out_degree[node] > 0; --k) {
				int output_node = degree_list[degree][k];
				out_degree[node]--;
				 in_degree[output_node]--;
				
				fout << node << ' ' << output_node << '\n';
			}
		}
	}

	return 0;
}