Pagini recente » Cod sursa (job #1899254) | Cod sursa (job #3192978) | Cod sursa (job #1783817) | Cod sursa (job #1859657) | Cod sursa (job #181783)
Cod sursa(job #181783)
#include <stdio.h>
#define MAXN 205
#define min(x, y) ((x)<(y)?(x):(y))
#define abs(x) ((x)>0?x:-x)
int n, m, s, d, viz[MAXN], Q[MAXN];
int C[MAXN][MAXN]; //capacitatea fiecarui arc
int F[MAXN][MAXN]; //fluxul fiecarui arc
void citire(void);
void ek(void); //Edmonds-Karp
void afisare(void);
int bfs(void);
int main(){
citire();
ek();
afisare();
return 0;
}
void citire(){
FILE *f=fopen("harta.in", "r");
int i, j, x, y;
fscanf(f, "%d", &n);
s=2*n+1; d=2*n+2;
for(i=1; i<=n; i++){
fscanf(f, "%d %d", &x, &y);
C[s][i]=x; C[i+n][d]=y;
}
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
if(i!=j)
C[i][j+n]=1;
n=2*n+2;
}
void afisare(){
FILE *g=fopen("harta.out", "w");
int i, j, vf=0;
for(i=1; i<=n; i++) vf+=F[i][d];
fprintf(g, "%d\n", vf);
n=(n-2)/2;
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
if(F[i][j+n])
fprintf(g, "%d %d\n", i, j);
}
void ek(){
int i, a, b, lg, v;
int L[MAXN];
do{
//marcam varfurile intr-o parcuregre in latime
for(i=1; i<=n; i++) viz[i]=0;
if(bfs()) return ;
//determin lantul de ameliorare L
L[0]=d; lg=0;
a=b=10000;
while(L[lg]!=s){
++lg;
L[lg] = abs(viz[L[lg-1]]);
if(viz[L[lg-1]]>0)
a = min(a, C[L[lg]][L[lg-1]]-F[L[lg]][L[lg-1]]);
else if(viz[L[lg-1]]<0)
b = min(b, F[L[lg-1]][L[lg]]);
}
v = min(a, b);
for(i=lg; i>0; i--)
if(viz[L[i-1]]>0)
F[L[i]][L[i-1]]+=v;
else
F[L[i-1]][L[i]]-=v;
} while(1);
}
int bfs(){
//returneaza 1 daca destinatia retelei nu a fost marcata
int p, u, i, x;
Q[0]=s; p=u=0; viz[s]=1;
while(p<=u && !viz[d]){
x=Q[p++];
for(i=1; i<=n; i++)
if(!viz[i])
if(F[x][i]<C[x][i]){
viz[i]=x; Q[++u]=i;
}
else if(F[i][x]>0){
viz[i]=-x; Q[++u]=i;
}
}
return !viz[d];
}