最大流无流量(邻接阵形式).txt

normal template for acm/ICPC

//求网络最大流,邻接阵形式
//返回最大流量
//传入网络节点数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;
	}
}