Pagini recente » Cod sursa (job #2861980) | Cod sursa (job #3146778) | Cod sursa (job #3004321) | Cod sursa (job #733893) | Cod sursa (job #2960532)
/*
Ideea de rezolvare a algoritmului este urmatoarea:
Folosim algoritmul de Max Flow. In plus, folosim optimizarea mentionata pe infoarena: La fiecare pas construim arborele BFS (excluzand destinatia),
si acum un drum de la sursa la destinatie e reprezentat de un drum de la sursa (care este radacina arborelui) la o frunza legata de destinatie printr-o
muchie nesaturata. Astfel putem la un pas sa marim fluxul pe un numar maximal de astfel de drumuri, fara a mai reface BFS-ul. Aceasta optimizare
reduce destul de mult timpul de executie.
Aici vine partea specifica problemei. Acestia sunt pasii rezolvarii:
Cream o dublura pentru fiecare nod.
Conectam toate nodurile la dubluri, mai putin la propria dublura, printr-o muchie de capacitate 1.
Adaugam nodul sursa si nodul destinatie.
Conectam sursa la toate nodurile originale prin muchii cu capacitatea egala cu gradul extern al nodurilor.
Conectam toate dublurile la destinatie prin muchii cu capacitatea egala cu gradul intern al nodurilor originale.
Aplicam MaxFlow
Muchiile saturate (cele care au capacitate 1 in graf si capacitate 0 in graful rezidual) dintre noduri si dubluri sunt muchiile grafului orientat
Complexitate:
Fie n = numarul de noduri, m = numarul de muchii
Timp: O(n*m^2) ///totusi, avem optimizarea cu arborele BFS
Memorie: O(n^2) ///matrice de adiacenta
*/
#include <bits/stdc++.h>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
int n,m,s,t;
int viz[205];
int parinte[205];
int graf[205][205];
int graf_rez[205][205];
long long flux_maxim;
void AddMuchie(int x, int y, int c)
{
graf_rez[x][y]=graf[x][y]=c;
}
bool bfs()
{
memset(viz,0,sizeof(viz));
memset(parinte,0,sizeof(parinte));
queue <int> q;
viz[s]=1;
q.push(s);
parinte[s]=-1;
while(!q.empty())
{
int act=q.front();
q.pop();
if(act==t) ///am ajuns la nodul t, deci exista un drum de la s la t pe care nu l-am saturat
return true;
for(int i=0;i<=2*n+1;i++) ///ne uitam prin vecinii nodului actual
if(viz[i]==0 && graf_rez[act][i]>0) ///nodul nu e vizitat, iar muchia (fie ea din graful rezidual sau nu) mai accepta flux
{
viz[i]=1;
parinte[i]=act;
q.push(i);
}
}
return false;
}
int maxFlow()
{
while(bfs()) ///cat timp mai exista drumuri nesaturate de la s la t
{
for(int i=0;i<=2*n;i++)
{ if(viz[i]!=0 && graf_rez[i][t]>0)
{
int aux_flux=1<<30; ///facem asta ca sa luam minimul de pe drum
parinte[t]=i;
int j=t;
while(parinte[j]!=-1) ///calatorim din tata in tata pana ajungem la s si vedem cat flux putem baga pe drumul ala (bottleneck inclus)
{
aux_flux=min(aux_flux,graf_rez[parinte[j]][j]);
j=parinte[j];
}
if(aux_flux!=0) ///Putem adauga flux pe drum
{
int j=t;
while(parinte[j]!=-1) ///mergem din tata in tata si modificam muchiile pe graful normal + cel rezidual
{
graf_rez[parinte[j]][j]-=aux_flux;
graf_rez[j][parinte[j]]+=aux_flux;
j=parinte[j];
}
flux_maxim=flux_maxim+aux_flux; ///adaugam la flux_maxim fluxul pe care il avem pe drumul calculat
}
}
}
}
return flux_maxim;
}
int main()
{
f>>n;
s=0;
t=2*n+1;
int x,y;
for(int i=1;i<=n;i++)
{
f>>x>>y;
AddMuchie(s,i,x);
AddMuchie(n+i,t,y);
}
for(int i=1;i<=n;i++)
for(int j=n+1;j<=2*n;j++)
if(i!=j-n)
AddMuchie(i,j,1);
g<<maxFlow()<<'\n';
for(int i=1;i<=n;i++)
for(int j=n+1;j<=2*n;j++)
if(graf[i][j]==1 && graf_rez[i][j]==0)
g<<i<<' '<<j-n<<'\n';
return 0;
}