Pagini recente » Cod sursa (job #2072753) | Monitorul de evaluare | Cod sursa (job #2447764) | Cod sursa (job #972445) | Cod sursa (job #2961279)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
vector<vector<int> > la;
vector<int> tata;
int n, dest, x,y, cap[201][201], maxim=999999;
int cmax = 0;
//BFS clasic
bool BFS()
{
vector<int> viz(2 * n + 1);
queue<int> q;
q.push(0);
viz[0] = 1;
tata[0] = -1;
while(!q.empty())
{
int u = q.front();
q.pop();
//for(auto v: la[u])
for(int i=0;i<la[u].size();i++)
{
int v=la[u][i];
if(viz[v]==0 && cap[u][v]!=0)
{
tata[v] = u;
if(v == dest)
return true;
viz[v] = 1;
q.push(v);
}
}
}
return false;
}
int Edmonds_Karp()
{
while(BFS())
{
int aux, next=dest, path_flow = maxim;
while(next != 0)
{
aux = tata[next];
path_flow=min(cap[aux][next],path_flow);
next = tata[next];
}
next=dest;
while(next != 0)
{
aux = tata[next];
cap[aux][next] -= path_flow;
cap[next][aux] += path_flow;
next = tata[next];
}
cmax = cmax + path_flow;
}
return cmax;
}
int main()
{
//citim nr de muchii
f >> n;
dest= 2 * n + 1;
la.resize(201);
tata.resize(2 * n + 1);
// cream un graf complet de n noduri cu ajutorul caruia avem in stanga nodurile propriu zise si in dreapta copiile lor
// adaugam capacitatea 1 pe muchia dintre ele
for(int i=1; i <= n; i++)
for(int j= 1 + n; j <= 2 * n; j++)
{
if(i!= j - n)
{
la[i].push_back(j);
la[j].push_back(i);
cap[i][j]=1;
}
}
// legam nodurile de un nod fictiv 0 pentru gradul intern - capacitatea e gradul intern
//legam o copie a nodurilor de un nod fictiv 2*n+1 pentru gradul extern - capacitatea e gradul extern
for(int i=1; i <= n; i++)
{
f >> x >> y;
la[0].push_back(i);
la[i].push_back(0);
la[dest].push_back(i + n);
la[i + n].push_back(dest);
cap[0][i]=x;
cap[i + n][dest]=y;
}
g<<Edmonds_Karp()<<endl;
//afisam perechiile de noduri care au muchii intre ele
for(int i=1; i <= n; i++)
for(int j= 1 + n; j <= 2 * n; j++)
{
if(cap[j][i])
g << i << " " << j - n << "\n";
}
return 0;
}