Pagini recente » Cod sursa (job #2202415) | Cod sursa (job #2328611) | Cod sursa (job #2632977) | Cod sursa (job #3126115) | Cod sursa (job #3193515)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <array>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
vector<int>parinte(203);
array<vector<int>,203>G;
int n,graf_rezidual[203][203],grad_in[203],grad_out[203];
int BFS(vector<int>& parinte)
{
queue<int> Q;
int i,nod,s=0,t=2*n+1;
for(i=1;i<2*n+2;i++)
parinte[i]=-1;//se seteaza toate nodurile nevizitate
Q.push(s);
parinte[s]=0;//parintele sursei e setat ca vizitat
//daca nu am vizitat nodul il adaugam si il setam ca vizitat pana cand se ajunge in t
while(Q.size()>0)
{
nod=Q.front();
Q.pop();
for(auto i:G[nod])
if(graf_rezidual[nod][i]&&parinte[i]==-1)
{
parinte[i]=nod;
if(t!=i)
Q.push(i);
else
return 1;
}
}
return 0;
}
int main()
{
int i,s=0,j,t,flux_maxim=0,nod,nod2,flux=INT_MAX;
//citesc datele
//s si t sunt 0 si n*2+!
fin >> n;
t=2*n+1;
for (i=1;i<n+1;i++)
fin>>grad_out[i]>>grad_in[i];
//adaug in graf muchii de la sursa la primul set si de la al doilea set la t pentru BFS
//in graful rezidual setez capacitatile egale cu cate drumuri ies sau intra in oras
for(i=1;i<n+1;i++)
{
G[i].push_back(s);
G[s].push_back(i);
G[n+i].push_back(t);
G[t].push_back(n+i);
graf_rezidual[s][i]=grad_out[i];
graf_rezidual[n+i][t]=grad_in[i];
}
//intre primul si al doilea set de orase setez capacitatea 1 pentru ca poate exista maxim 1 drum intre 2 orase daca acestea nu sunt identice
for(i=1;i<n+1;i++)
for(j=n+1;j<2*n+1;j++)
if(j==n+i)
graf_rezidual[i][j]=0;
else
{
G[i].push_back(j);
G[j].push_back(i);
graf_rezidual[i][j]=1;
}
//cat timp gasesc drumuri gasesc fluxul maxim posibil pe acel drum, updatez graful rezidual de la t la s si suma fluxurilor
while(BFS(parinte)==1)
{
nod=t;
while(nod!=s)
{
nod2=parinte[nod];
if (flux>graf_rezidual[nod2][nod])
flux=graf_rezidual[nod2][nod];
nod=nod2;
}
nod=t;
while(nod!=s)
{
nod2=parinte[nod];
graf_rezidual[nod][nod2]=graf_rezidual[nod][nod2]+flux;
graf_rezidual[nod2][nod]=graf_rezidual[nod2][nod]-flux;
nod=nod2;
}
flux_maxim=flux_maxim+flux;
}
fout<<flux_maxim<<"\n";
//daca orasele nu sunt identice si capacitatea pe graful rezidual e 0 inseamna ca exista un drum intre orase si le afisez
for(i=1;i<=n;i++)
{
for(j=n+1;j<2*n+1;j++)
if (graf_rezidual[i][j]==0)
fout<<i<<" "<<j-n<<"\n";
}
return 0;
}