Pagini recente » Cod sursa (job #2246153) | Cod sursa (job #2396184) | Cod sursa (job #1925475) | Cod sursa (job #977949) | Cod sursa (job #2958819)
#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
#include <algorithm>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
int c[1024][1024]; //capacitate intre doua noduri
int f[1024][1024]; //capacitate consumata
int tata[1024]; //tatal fiecarui nod
vector<int> la[1024];
//int coada[1024];
vector<int> vizitat;
int nod,n,m,x,y,z,i,j,minn,flow,sursa,destinatie;
int bfs()
{
vizitat.assign(n+n+2, 0);
queue<int> coada;
coada.push(0);
//vizitat[sursa]=1;
while(!coada.empty())
{
nod=coada.front();
coada.pop();
vizitat[nod]=1;
if(nod == n+n+1) break; //opresc parcurgerea daca ajung la destinatie
for(int j=0;j<la[nod].size();j++)
{
if(vizitat[la[nod][j]]==0 && c[nod][la[nod][j]]!=f[nod][la[nod][j]]) //daca nu e vizitat si daca drumul nu a fost consumat
{
coada.push(la[nod][j]);
vizitat[la[nod][j]]=1;
tata[la[nod][j]]=nod; //retin tatal nodului
}
}
}
return vizitat[n];//ne zice daca a ajuns la final drumul -> nu s a gasit fluxul maxim deci continuam
}
int main()
{
fin>>n;
sursa=0;
destinatie=n+n+1;
///dublez nodurile
for(i =1;i<=n;i++)
{
fin>>x>>y;
la[sursa].push_back(i);
la[i].push_back(sursa);
la[destinatie].push_back(n+i);
la[n+i].push_back(destinatie);
c[0][i] =x;
c[i+n][n+n+1]=y;
}
for(i =1;i<=n;i++)
{
for(j=1+n;j<=n+n;j++)
{
if(i!=j-n) //intre nod si dublura lui nu e muchie
{
c[i][j]=1;//intre oricare nod si alta dublura am muchie
la[i].push_back(j);
la[j].push_back(i);
}
}
}
flow=0;
while(bfs())
{
for(i=0;i<la[n+n+1].size();i++)
{
nod = la[n+n+1][i];
if (f[nod][n+n+1] == c[nod][n+n+1] || !vizitat[nod]) continue;
tata[n+n+1] = nod;
int minn=9999999;
for (j =n+n+1; j>0; j = tata[j])
{
minn = min(minn, c[tata[j]][j] - f[tata[j]][j]); //calculez capacitatea minima a drumului (capacitate totala-consumata)
}
if (minn == 0) continue;
for (j =n+n+1; j>0; j = tata[j]) //modific capacitatile drumurilor+ maresc flowul rezidual
{
f[tata[j]][j] += minn;
f[j][tata[j]] -= minn;
}
flow=flow+minn;
}
}
fout<<flow<<'\n';
for (i = 1; i <= n; ++i){
for (j=0;j<la[i].size();j++)
{
if(la[i][j]!=0 && f[i][la[i][j]]!=0)
fout<<i<<' '<<la[i][j]-n<<'\n';
}
}
return 0;
}