Pagini recente » Cod sursa (job #810411) | Cod sursa (job #900181) | Cod sursa (job #2912070) | Cod sursa (job #1548099) | Cod sursa (job #3190600)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
class graph{
private:
vector<vector<int>> cap;
vector<vector<int>> flux;
vector<bool> vizitat;
vector<int> tati;
int n,start,end,size;
public:
graph(int n):n(n){
size = 2 * n + 3;
start = 2*n+1;
end = 2*n+2;
init();
citire();
}
void init(){
cap.resize(size, vector<int>(size, 0));
flux.resize(size, vector<int>(size, 0));
vizitat.resize(size,false);
tati.resize(size,-1);
}
void citire(){
int x,y;
for(int i=1;i<=n;i++) {
fin >> x >> y;
addMuchie(x, y, i);
}
}
bool bfs(){
for(int i=1;i<=2*n+2;i++)
vizitat[i]= false;
queue<int> q;
q.push(start);
while (!q.empty()) {
int u = q.front();
vizitat[u]=true;
q.pop();
for (int v = 1; v < end+1; v++) {
if (!vizitat[v] && cap[u][v]-flux[u][v] > 0) {
q.push(v);
tati[v] = u;
vizitat[v] = true;
if(v == end)
return true;
}
}
}
return false;
}
int fordFulkerson()
{
int raspuns = 0;
while (bfs()) {
int current, next;
int minim = INT_MAX;
next=tati[end],current=end;
while(next!=-1) {
minim = min(minim, cap[next][current]-flux[next][current]);
current=next;
next=tati[current];
}
next=tati[end],current=end;
while(next!=-1) {
flux[current][next] -= minim;
flux[next][current] += minim;
current=next;
next=tati[current];
}
raspuns += minim;
}
return raspuns;
}
void addMuchie(int a, int b, int i)
{
cap[start][i]=a;
cap[n+i][end]=b;
for(int j=1;j<=n;j++)
if(i!=j)
cap[i][n+j]=1;
}
void afisare(){
fout << fordFulkerson() <<endl;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(flux[i][n+j]==1)
fout<<i<<" "<<j<<endl;
}
};
int main()
{
int n,a,b;
fin >> n;
graph graf(n);
graf.afisare();
return 0;
}