Cod sursa(job #3190474)

Utilizator daria_lapadusLapadus Daria daria_lapadus Data 7 ianuarie 2024 17:22:15
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.58 kb
#include <fstream>
#include <queue>
using namespace std;

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

int N;  // Nr de orase.
int C[205][205];  // Matricea care va conține capacitatea initiala a graficului.
int residualGraph[205][205];  // Matricea pentru graficul rezidual.
int parent[205];  // Vector pentru stocarea caii în BFS.
bool visited[205];  // Vector pentru marcarea nodurilor vizitate.

// Funcția BFS pentru a gasi o cale de la sursa la destinatie in graficul rezidual.
bool bfs(int residualGraph[][205], int s, int t, int parent[])
{
    // Initializez visited cu false pentru toate nodurile.
    for (int i = 0; i <= 2*N+1; i++)
		visited[i] = false;

    queue<int> q;  // Coada pentru BFS.
    q.push(s);  // Incep de la nodul sursa.
    visited[s] = true;  // Marchez sursa ca vizitata.
    parent[s] = -1;  // Sursa nu are parinte.

    // BFS.
    while (!q.empty())
    {
        int u = q.front();  // Obtin nodul curent.
        q.pop();

        // Verific pentru fiecare nod v daca este nevizitat si exista o muchie de la u la v.
        for (int v = 0; v <= 2*N+1; v++)
        {
            if (visited[v] == false && residualGraph[u][v] > 0)
            {
                q.push(v);  // Adaug v in coada.
                parent[v] = u;  // Setez parintele lui v ca fiind u.
                visited[v] = true;  // Marchez v ca vizitat.
            }
        }
    }

    // Returnz true daca a gasesc o cale pana la destinatie.
    return (visited[t] == true);
}

// Algoritmul Ford-Fulkerson pentru gasirea fluxului maxim.
int fordFulkerson(int graph[][205], int s, int t)
{
    int u, v;

    // Fluxul maxim initializat la 0.
    int max_flow = 0;

    // BFS pentru a gasi toate caile posibile de la sursa la destinatie.
    while (bfs(residualGraph, s, t, parent))
    {
        // Gasesc fluxul minim pe calea gasita de BFS.
        int path_flow = 1000000;
        for (v = t; v != s; v = parent[v])
        {
            u = parent[v];
            path_flow = min(path_flow, residualGraph[u][v]);
        }

        // Actualizez capacitatea reziduala a muchiilor si adaug fluxul caii la fluxul total.
        for (v = t; v != s; v = parent[v])
        {
            u = parent[v];
            residualGraph[u][v] -= path_flow;
            residualGraph[v][u] += path_flow;
        }

        // Adaug fluxul caii la fluxul total.
        max_flow += path_flow;
    }

    return max_flow;
}

int main()
{
    // Citesc numarul de orase.
	fin >> N;

    // Initializez matricea C cu capacitatile drumurilor.
	for (int i = 1; i <= N; i++)
	{
		int dext, dint;
		fin >> dext >> dint;  // Citesc gradele de iesire si intrare pentru fiecare oras.
		C[0][i] = dext;  // Setez gradul de iesire in matrice.
		C[i+N][2*N+1] = dint;  // Setez gradul de intrare in matrice.
	}

    // Creez muchiile intre nodurile corespunzatoare oraselor.
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			if (i != j)
				C[i][j+N] = 1;  // Setez o capacitate de 1 pentru fiecare muchie posibila intre doua orase diferite.

    // Copiez matricea C in graficul rezidual.
	for (int i = 0; i <= 2*N+1; i++)
		for (int j = 0; j <= 2*N+1; j++)
			residualGraph[i][j] = C[i][j];

    // Afisez fluxul maxim si reconstruiesc drumurile initiale.
	fout << fordFulkerson(C, 0, 2*N+1) << "\n";

    // Afisez drumurile care au fost folosite in graficul final.
	for (int i = 1; i <= N; i++)
		for (int j = N+1; j <= 2*N; j++)
			if (residualGraph[i][j] == 0 && C[i][j] == 1)
				fout << i << " " << j-N << "\n";

	return 0;
}