Pagini recente » Cod sursa (job #2517114) | Cod sursa (job #1538615) | Cod sursa (job #2815322) | Cod sursa (job #1877736) | Cod sursa (job #2960867)
#include <iostream>
#include <fstream>
#include <vector>
#include <climits>
#include <queue>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
vector<vector<int>> la;
int capacitate[201][201], maxim=INT_MAX;
long max_flow = 0;
vector<int> parinte;
int M,dest;
int bfs()
{
vector<bool> viz(2 * M + 1);
queue<int> coada;
coada.push(0);
viz[0] = true;
parinte[0] = -1;
while(!coada.empty())
{
int u = coada.front();
coada.pop();
for(auto v: la[u])
{
if(viz[v]==false && capacitate[u][v]!=0)
{
parinte[v] = u;
if(v == dest)
return 1;
viz[v] = true;
coada.push(v);
}
}
}
return 0;
}
int EdmondsKarp()
{
int new_flow=bfs();
while(new_flow)
{
int temp, next=dest, path_flow = maxim;
while(next != 0)
{
temp = parinte[next];
path_flow=min(capacitate[temp][next],path_flow);
next = parinte[next];
}
next=dest;
while(next != 0)
{
temp = parinte[next];
capacitate[temp][next] -= path_flow;
capacitate[next][temp] += path_flow;
next = parinte[next];
}
max_flow = max_flow + path_flow;
new_flow=bfs();
}
fout<<max_flow<<"\n";
}
int main()
{
fin >> M;
int a,b;
la.resize(201);
parinte.resize(2 * M + 1);
dest= 2 * M + 1;
for(int i=1; i <= M; i++)
{
fin>>a>>b;
la[0].push_back(i);
la[i].push_back(0);
la[dest].push_back(i + M);
la[i + M].push_back(dest);
capacitate[0][i]=a;
capacitate[i + M][dest]=b;
}
for(int i=1; i <= M; i++)
for(int j= 1 + M; j <= 2 * M; j++)
{
if(i!= j - M)
{
la[i].push_back(j);
la[j].push_back(i);
capacitate[i][j]=1;
}
}
EdmondsKarp();
for(int i=1; i <= M; i++)
for(int j= 1 + M; j <= 2 * M; j++)
{
if(capacitate[j][i]==1)
fout << i << " " << j - M << "\n";
}
return 0;
}