Pagini recente » Cod sursa (job #1022784) | Cod sursa (job #2177399) | Cod sursa (job #1613852) | Cod sursa (job #2730985) | Cod sursa (job #3190474)
#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;
}