Pagini recente » Cod sursa (job #1924101) | Cod sursa (job #1687421) | Cod sursa (job #584057) | Cod sursa (job #524189) | Cod sursa (job #3186754)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
class graph{
private:
vector<vector<int>> muchii;
vector<vector<int>> rezidual;
int n;
vector<bool> vizitat;
vector<int> tata;
int s,t;
public:
graph(int n):n(n){
muchii.resize(2*n+3, vector<int>(2*n+3, 0));
rezidual.resize(2*n+3, vector<int>(2*n+3, 0));
vizitat.resize(2*n+3,false);
tata.resize(2*n+3,-1);
s=2*n+1;
t=2*n+2;
}
bool bfs(){
queue<int> q;
q.push(s);
while (!q.empty()) {
int u = q.front();
////cout<<u<<endl;
vizitat[u]=true;
q.pop();
for (int v = 1; v < t+1; v++) {
///cout<<muchii[u][v]-rezidual[u][v]<<endl;
if (!vizitat[v] && muchii[u][v]-rezidual[u][v] > 0) {
if(v==t)
{
tata[v] = u;
vizitat[v] = true;
return true;
}
q.push(v);
tata[v] = u;
vizitat[v] = true;
///cout<<v<<endl;
}
}
}
return false;
}
void fordFulkerson()
{
int u, v;
/*or (u = 0; u < t+1; u++)
for (v = 0; v < t+1; v++)
rezidual[u][v] = muchii[u][v];*/
int max_flow = 0;
while (bfs()) {
int path_flow = INT_MAX;
v=tata[t],u=t;
///cout<<"v "<<v<<endl;
while(v!=-1) {
path_flow = min(path_flow, muchii[v][u]-rezidual[v][u]);
u=v;
v=tata[u];
///cout<<"p "<<path_flow<<endl;
}
v=tata[t],u=t;
while(v!=-1) {
rezidual[u][v] -= path_flow;
rezidual[v][u] += path_flow;
///cout<<"r "<<rezidual[u][v]<<" "<<rezidual[v][u]<<endl;
u=v;
v=tata[u];
///cout<<"r "<<rezidual[u][v]<<" "<<rezidual[v][u]<<endl;
}
max_flow += path_flow;
for(int i=1;i<=2*n+2;i++)
{
//cout<<"ok"<<endl;
vizitat[i]= false;
}
}
g<<max_flow<<endl;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(rezidual[i][n+j]==1)
{
g<<i<<" "<<j<<endl;
}
}
}
}
void addMuchie(int a, int b, int i)
{
muchii[2*n+1][i]=a;
muchii[n+i][2*n+2]=b;
///cout<<muchii[2*n+1][i]<<" "<<muchii[n+i][2*n+2]<<endl;
for(int j=1;j<=n;j++)
if(i!=j)
muchii[i][n+j]=1;
}
};
int main()
{
int n,a,b;
f>>n;
graph graf(n);
int s=2*n+1,t=2*n+2;
for(int i=1;i<=n;i++)
{
f>>a>>b;
graf.addMuchie(a,b,i);
}
graf.fordFulkerson();
return 0;
}