最短增广路求最大流.cpp

来自「求最大增广路的算法。」· C++ 代码 · 共 45 行

/*
**最短增广路算法.
*/

#include <stdio.h>
#include <string.h>
int C[10][10];

main()
{
	int head=1,tail=1,queue[100],d[100],flag[100],s,t,q,p,w,m,n,i,j,node;
	memset(C,0,sizeof(C));
	memset(flag,0,sizeof(flag));
	scanf("%d%d",&n,&m);
	s=1;t=n;
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&p,&q,&w);
		C[p][q]=w;
	}
	
	queue[1]=t; d[t]=0;
	while(head<=tail)
	{
		node=queue[head];
		for(i=1;i<=n;i++)
		{
			if(C[i][node]>0&&flag[i]==0)
			{
				tail++;
				queue[tail]=i;
				d[i]=d[node]+1;
				flag[i]=1;
			}
		}
		head++;
	}
	for(i=1;i<=t;i++)
	printf("%d ",d[i]);
	
	while(1);
}