Pagini recente » Cod sursa (job #2937072) | Cod sursa (job #3137958) | Cod sursa (job #890552) | Cod sursa (job #2899851) | Cod sursa (job #2962380)
// 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;
}