Pagini recente » Cod sursa (job #1941186) | Cod sursa (job #1111357) | Cod sursa (job #678821) | Cod sursa (job #358457) | Cod sursa (job #2970183)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
// Se creeaza un graf complet de n noduri. In stanga nodurile propriu zise si in dreapta copiile lor
// Se initializeaza muchia dintre ele cu capacitatea 1
// Se leaga nodurile de un nod fictiv 0 pentru gradul intern si o copie a nodurilor de nodul fixtiv 2*n+1
// Se foloseste un bfs pentru a traversa graful si se calculeaza flow-ul minim
// Se parcurge drumul si se scade din flow ul fiecarui nod flow ul minim
// Flow-ul maxim va fi numarul de drumri si pentru a afisa drumurile se va itera vectorul de capacitati si se vor extrage perechile de noduri cu capacitatile 1
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
vector<vector<int>> adj_list;
vector<int> parent;
int N, dest, x,y, capacity[201][201], maxim=1000000;
long max_flow = 0;
//parcurgere de tip BFS
bool bfs()
{
vector<bool> viz(2 * N + 1);
queue<int> q;
q.push(0);
viz[0] = true;
parent[0] = -1;
while(!q.empty())
{
int u = q.front();
q.pop();
for(auto v: adj_list[u])
{
if(viz[v]==false && capacity[u][v]!=0)
{
parent[v] = u;
if(v == dest)
return true;
viz[v] = true;
q.push(v);
}
}
}
return false;
}
int main()
{
f >> N;
dest= 2 * N + 1;
adj_list.resize(201);
parent.resize(2 * N + 1);
// Initializare
for(int i=1; i <= N; i++)
for(int j= 1 + N; j <= 2 * N; j++)
{
if(i!= j - N)
{
adj_list[i].push_back(j);
adj_list[j].push_back(i);
capacity[i][j]=1;
}
}
// Legare noduri de nodul 0 si 2*n+1 pentru gradele interne si externe
for(int i=1; i <= N; i++)
{
f >> x >> y;
adj_list[0].push_back(i);
adj_list[i].push_back(0);
adj_list[dest].push_back(i + N);
adj_list[i + N].push_back(dest);
capacity[0][i]=x;
capacity[i + N][dest]=y;
}
while(bfs())
{
int aux, next=dest, path_flow = maxim;
while(next != 0)
{
aux = parent[next];
path_flow=min(capacity[aux][next],path_flow);
next = parent[next];
}
next=dest;
while(next != 0)
{
aux = parent[next];
capacity[aux][next] -= path_flow;
capacity[next][aux] += path_flow;
next = parent[next];
}
max_flow = max_flow + path_flow;
}
g<<max_flow<<"\n";
// Afisare
for(int i=1; i <= N; i++)
for(int j= 1 + N; j <= 2 * N; j++)
{
if(capacity[j][i])
g << i << " " << j - N << "\n";
}
return 0;
}