Pagini recente » Cod sursa (job #1986501) | Cod sursa (job #3215263) | Cod sursa (job #43064) | Cod sursa (job #1547980) | Cod sursa (job #2961636)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
#define sz 201
vector<vector<int>> adj_list;
int capacity[sz][sz];
vector<int> parent;
int a,b,n,s,t;
bool BFS()
{
vector<bool> viz(t);
queue<int> coada;
coada.push(s);
viz[s]=true;
parent[s]=-1;
while(!coada.empty())
{
int u=coada.front();
coada.pop();
for(auto v:adj_list[u])
{
if(viz[v]==false && capacity[u][v]!=0)
{
parent[v]=u;
if(v==t)
return true;
viz[v]=true;
coada.push(v);
}
}
}
return false;
}
int EdmondsKarp()
{
long maxFlow=0;
while(BFS()==true)
{
int u,v=t;
int pathFlow=INT_MAX;
while(v!=s)
{
u=parent[v];
if(capacity[u][v]<pathFlow)
pathFlow=capacity[u][v];
v=parent[v];
}
v=t;
while(v!=s)
{
u=parent[v];
capacity[u][v]-=pathFlow;
capacity[v][u]+=pathFlow;
v=parent[v];
}
maxFlow+=pathFlow;
}
return maxFlow;
}
void afisare()
{
fout<<EdmondsKarp()<<"\n";
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++)
if (capacity[j+n][i] == 1)
fout<<i<<" "<<j<<endl;
}
void citire()
{
fin>>n;
s=0;
t=2*n+1;
parent.resize(2*n+1);
adj_list.resize(sz);
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
{
if(i!=j)
{
adj_list[i].push_back(j+n);
adj_list[j+n].push_back(i);
capacity[i][j+n]=1;
}
}
for (int i=1; i<=n; i++)
{
int x,y;
fin>>x>>y;
adj_list[s].push_back(i);
adj_list[i].push_back(s);
capacity[s][i]=x;
adj_list[t].push_back(i+n);
adj_list[i+n].push_back(t);
capacity[i+n][t]=y;
}
afisare();
}
int main()
{
citire();
return 0;
}