Cod sursa(job #298658)

Utilizator rurutzairimia ruxandra maria rurutza Data 6 aprilie 2009 11:52:49
Problema Flux maxim Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include<fstream.h>
ifstream f("maxflow.in");
ofstream g("maxflow.out");
#define MAXN 701
long n,m,x,y,i,cp,flux,fmin;
int a[MAXN][MAXN],c[MAXN][MAXN],ff[MAXN][MAXN],tata[MAXN];
int bfs()
{
int p=1,u=1,ok=0,i,x,y;
int q[MAXN];
q[1]=1;
for(i=1;i<=n;i++)
tata[i]=0;
while(p<=u)
{
x=q[p];
for(i=1;i<=a[x][0];i++)
{
y=a[x][i];
if(!tata[y]&&c[x][y]>ff[x][y])
{if(y==n)
{
ok=1;
}
else
{tata[y]=x;
u++;
q[u]=y;
}
}}
p++;
}
return ok;
}
int main()
{
f>>n>>m;
n=n;
for(i=1;i<=m;i++)
{
f>>x>>y>>cp;
c[x][y]=cp;
a[x][++a[x][0]]=y;
a[y][++a[y][0]]=x;
}
while(bfs())
{
for(i=1;i<=a[n][0];i++)
if(tata[a[n][i]])
{
y=a[n][i];
fmin=c[y][n]-ff[y][n];
while(y!=1)
{
if(c[tata[y]][y]-ff[tata[y]][y]<fmin)
fmin=c[tata[y]][y]-ff[tata[y]][y];
y=tata[y];
}
y=a[n][i];
ff[y][n]=ff[y][n]+fmin;
ff[n][y]-=fmin;
while(y!=1)
{
ff[tata[y]][y]+=fmin;
ff[y][tata[y]]-=fmin;
y=tata[y];
}
flux+=fmin;
}
}
g<<flux<<"\n";
f.close();
g.close();
return 0;
}