以下是我的代碼：
#include<stdio.h>
const long maxn=107,INF=2000007;
typedef struct
{
long front,rear,count,item[maxn];
}queue;
void clear(queue &q)
{
q.count=0;
q.front=0;
q.rear=-1;
}
bool empty(queue &q)
{
return (q.count==0);
}
void push(queue &q,long x)
{
q.rear++;
q.item[q.rear]=x;
q.count++;
}
void pop(queue &q,long &x)
{
x=q.item[q.front];
q.front++;
q.count--;
}
// Queue
long n,m,cap[maxn][maxn],flow[maxn][maxn];
long s,t,fmax;
long min(long a,long b)
{
return (a<b?a:b);
}
void read()
{
scanf("%ld%ld",&n,&m);
s=1;t=n;
for(long i=1;i<=n;i++)
for(long j=1;j<=n;j++)
cap[i][j]=0;
for(long i=1;i<=m;i++)
{
long a,b,w;
scanf("%ld%ld%ld",&a,&b,&w);
cap[a][b]=w;
}
}
void EK()
{
long tmp[maxn],father[maxn];
queue q;clear(q);
for(long i=1;i<=n;i++)
for(long j=1;j<=n;j++)
flow[i][j]=0;
fmax=0;
while(true)
{
for(long i=1;i<=n;i++) tmp[i]=father[i]=0;
tmp[s]=INF;
push(q,s);
while(!empty(q))
{
long i;
pop(q,i);
for(long j=1;j<=n;j++)
if(!tmp[j]&&cap[i][j]>flow[i][j])
{
tmp[j]=min(tmp[i],cap[i][j]-flow[i][j]);
father[j]=i;
push(q,j);
}
}
if(tmp[t]==0) break;
for(long i=t;i!=s;i=father[i])
{
flow[father[i]][i]+=tmp[t];
flow[i][father[i]]-=tmp[t];
}
fmax+=tmp[t];
}
printf("%ld\n",fmax);
}
int main()
{
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
read();
EK();
return 0;
}
posted on 2010-01-20 21:58
lee1r 閱讀(1760)
評論(0) 編輯 收藏 引用 所屬分類:
算法與數據結構