Pagini recente » Istoria paginii runda/summer_camp_9/clasament | Cod sursa (job #680782) | Cod sursa (job #345714) | Cod sursa (job #2056903) | Cod sursa (job #2958421)
#include <bits/stdc++.h>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
int n, in[101], out[101], capacitate[202][202], sursa, destinatie, parinte[202];
vector<int> muchii[202];
void citeste(), construiesteGrafulDeFlow(), afiseazaMuchiile();
int edmondsKarp();
int main()
{
citeste();
construiesteGrafulDeFlow();
g << edmondsKarp() << '\n';
afiseazaMuchiile();
return 0;
}
void afiseazaMuchiile()
{
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
if(i != j && capacitate[i][n + j] == 0)
g << i << " " << j << '\n';
}
bool bfs()
{
vector<bool> ap;
queue<int> q;
ap.resize(destinatie + 1);
// Adaug sursa in coada
q.push(sursa);
ap[sursa] = true;
// Cat timp mai am elemente in coada
while(!q.empty()){
int nod = q.front();
q.pop();
// Verific daca pot sa mai pun flow pe muchiile catre vecinii nodului curent
for(auto it : muchii[nod]){
// Daca vecinul nu e vizitat si se poate adauga flow pe muchia de la nod la el
if(!ap[it] && capacitate[nod][it]){
// Parintele vecinului este nodul curent si vecinul e vizitat si adaugat in coada
parinte[it] = nod;
ap[it] = true;
q.push(it);
// Daca vecinul este destinatia atunci am gasit un drum bun
if(it == destinatie)
return true;
}
}
}
// Daca ajung aici nu mai sunt drumuri bune
return false;
}
int edmondsKarp()
{
int raspuns = 0;
// Cat timp mai gasesc un drum pana la destinatie pe care pot adauga flow
while(bfs()) {
// Adaug la toate muchiile de pe drum 1
int nod = destinatie;
while(nod != sursa) {
int par = parinte[nod];
capacitate[par][nod] -= 1;
capacitate[nod][par] += 1;
nod = par;
}
// Adaug flow-ul gasit la raspuns
raspuns += 1;
}
return raspuns;
}
void construiesteGrafulDeFlow()
{
sursa = 0;
destinatie = 2 * n + 1;
// Sparg nodurile in doua unul care e conectat de sursa si unul care e conectat de destinatie
// Muchii de la sursa la noduri
for(int i = 1; i <= n; ++i) {
muchii[sursa].push_back(i);
capacitate[sursa][i] = in[i];
}
// Muchii de la noduri la destinatie
for(int i = 1; i <= n; ++i) {
muchii[n + i].push_back(destinatie);
capacitate[n + i][destinatie] = out[i];
}
// Muchiile intre noduri
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
if(i != j) {
muchii[i].push_back(n + j);
muchii[n + j].push_back(i);
capacitate[i][n + j] = 1;
}
}
void citeste()
{
f >> n;
for(int i = 1; i <= n; ++i)
f >> in[i] >> out[i];
}