Pagini recente » Cod sursa (job #1178100) | Cod sursa (job #1932306) | Cod sursa (job #1467135) | Cod sursa (job #174496) | Cod sursa (job #2691890)
#include <iostream>
#include <bits/stdc++.h>
#define maxim 2000000000
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
int n, dp[201], dm[201], graf[501][501], graf_rezidual[501][501], s, t, vizitat[501], tata[501], flux_maxim, suma_g;
vector<pair<int,int>> stuff[201];
int bfs()
{
queue<int> q;
tata[s] = -1;
q.push(s);
while(!q.empty())
{
int u = q.front();
q.pop();
for(int i = 0; i <= 2 * n + 1; i++)
if(!vizitat[i] && graf_rezidual[u][i] > 0)
{
q.push(i);
tata[i] = u;
vizitat[i] = 1;
}
}
return vizitat[t];
}
int FordFulkerson()
{
for(int i = 0; i <= 2 * n + 1; i++)
for(int j = 0; j <= 2 * n + 1; j++)
graf_rezidual[i][j] = graf[i][j];
flux_maxim = 0;
while(bfs())
{
for(int i = 0; i <= 2 * n + 1; i++)
vizitat[i] = 0;
int flux_curent = maxim;
int current = t;
while (current != s)
{
flux_curent = min(flux_curent, graf_rezidual[tata[current]][current]);
current = tata[current];
}
current = t;
while(current != s)
{
graf_rezidual[current][tata[current]] += graf_rezidual[tata[current]][current] > 0 ? flux_curent : -flux_curent;
graf_rezidual[tata[current]][current] -= graf_rezidual[tata[current]][current] > 0 ?flux_curent : flux_curent;
current = tata[current];
}
flux_maxim += flux_curent;
}
return flux_maxim;
}
int main() {
f >> n;
for(int i = 1; i <= n; i++)
{
f >> dp[i] >> dm[i]; //citim gradele de iesire (cu plus)
suma_g = dp[i];
}
s = 0; t = 2 * n + 1; //adaugam vf. de start si de final
for(int i = 1; i <= n; i++)
for(int j = n + 1; j <= 2 * n; j++) //contruim reteaua de transport (de la n+1 la 2*n cealalta parte a bipartitiei)
if(i != j - n)
{
graf[i][j] = 1;
stuff[i].emplace_back(j,1);
}
for(int i = 1; i <= n; i++)
{
graf[s][i] = dp[i]; //adaugam arce iesire
graf[n + i][t] = dm[i]; //adaugam arce intrare
}
flux_maxim = FordFulkerson(); //gasim fluxul maxim in retea
g << flux_maxim << '\n';
if(suma_g <= flux_maxim) //stabilim daca graful poate fi construit
{
for(int i = 1; i <= n; i++)
for(auto x : stuff[i])
if(x.second - graf_rezidual[i][x.first] != 0) //arcele cu flux pozitiv sunt arce in G
g << i << " " << x.first - n << '\n';
}
return 0;
}