最大流无流量(邻接阵形式)代码,C/C++代码库,德仔网

代码语言

代码分类

【C/C++】最大流无流量(邻接阵形式)

作者:Fitzgerald / 发布于2016/3/3/ 426

//求网络最大流,邻接阵形式
//返回最大流量
//传入网络节点数n,容量mat,源点source,汇点sink
//注意mat矩阵被修改

#define MAXN 100
#define inf 1000000000

int max_flow(int n,int mat[][MAXN],int source,int sink){
	int v[MAXN],c[MAXN],p[MAXN],ret=0,i,j;
	for (;;){
		for (i=0;i<n;i++)
			v[i]=c[i]=0;
		for (c[source]=inf;;){
			for (j=-1,i=0;i<n;i++)
				if (!v[i]&&c[i]&&(j==-1||c[i]>c[j]))
					j=i;
			if (j<0) return ret;
			if (j==sink) break;
			for (v[j]=1,i=0;i<n;i++)
				if (mat[j][i]>c[i]&&c[j]>c[i])
					c[i]=mat[j][i]<c[j]?mat[j][i]:c[j],p[i]=j;
		}
		for (ret+=j=c[i=sink];i!=source;i=p[i])
			mat[p[i]][i]-=j,mat[i][p[i]]+=j;
	}
}

评论列表

本站所提供的代码，版权归原作者所有，若有侵犯作者版权，请与我们联系，我们将立即删除或修改。谢谢!
本站所有代码发布及提供者。

试试其它关键字

同语言下

可能有用的

Fitzgerald贡献的其它代码(3)