//即数组被初始化为二进制的00000001 00000001 00000001 00000001 ，十进制为16843009
memset(gap,0,sizeof(gap));
queue
q.push(t);
level[t]=0;//汇点距离为0
gap[level[t]]++;
while(!q.empty())
{
int temp=q.front(); q.pop();
for(int i=1;i<=n;i++)
if(level[i]>n && map[i][temp]>0)
{
q.push(i);
level[i]=level[temp]+1;
gap[level[i]]++;
}
}
}
int fine_path(int u)//查找残量网络中是否有与u相连 且距离为1的点
{
for(int i=1;i<=n;i++) if(map[u][i]>0 && level[u]==level[i]+1)
return i;
return -1;
}
int Advance(int s,int t)//找到汇点时进行增广
{
int i,minflow=INF;
for(i=t;i!=s;i=fa[i]) if(minflow>map[fa[i]][i])//查找这条增广路中最小的流量
{
minflow=map[fa[i]][i];
}
for(i=t;i!=s;i=fa[i])
{
map[fa[i]][i]-=minflow;
map[i][fa[i]]+=minflow;//反向边也要操作
}
return minflow;
}
int retreat(int u)//对点u重新设置最小的距离
{
int fine=INF;
for(int i=1;i<=n;i++) if(map[u][i]>0 && fine>level[i]+1)
fine=level[i]+1;
if(fine==INF) fine=n;//找不到的话设置为最大，即点u不会再被经过
return fine;
int cxbsap(int s,int t)
{
sap_bfs(t);
int i,j,v,u=s,flow=0;//初始化
while(level[s]<=n)//源点与汇点距离小于n时执行，要是不存在源点到汇点的通路直接跳出
{
v=fine_path(u);// 找u的下一个点
if(v>0)
{
fa[v]=u;//找到后标记父节点
u=v;//把v赋值给u，如果不是汇点，直接跳回75行了
if(u==t)
{
flow+=Advance(s,t);
u=s;//找的一条路径后重新查找
}
}
else
{
if(--gap[level[u]]==0) return flow;//如果其中一个距离个数为0，即出现断层，没有通路看，直接跳出
v=retreat(u);
gap[v]++;
level[u]=v;
if(u!=s) u=fa[u];
}
}
return flow;
}
int main()
{
// freopen("in.txt","r",stdin);
int i,j,a,b,x;
while(~scanf("%d%d",&m,&n))
{
memset(map,0,sizeof(map));
for(i=0;i
scanf("%d%d%d",&a,&b,&x);
map[a][b]+=x;
}
int ans=cxbsap(1,n);
printf("%d\n",ans);
}
return 0;
}
作者：cxb569262726