maximum flow.txt

1.表达式求值；2.二分匹配模板；3.最大流；4.点到线段的距离；5.字符串字典顺序

/*

                                        网络最大流 <BFS算法>

*/

/* 
	步骤：1，BFS ；
*/

#include <stdio.h>
#define Max 2000000000     //初始值，与题目数据有关； 
#define N 418              //节点个数； 
struct node1{
	int ind;
	int prt;
} str[N];                  //BFS 时的保存数组；ind 为节点号; prt为父节点号； 
int mark[N];               //BFS 过程中的标记数组； 
int top;
int flag;                  //标记号； 
struct node{
	int max;           //i -- j 的最大流; 
	int tem;           //可行流<不断更新的>; 
}flow[N][N];
int n;                     //节点数； 
int s, t;                  //起点，终点； 
void max_flow(){           //流 flow[N][N]中的最大流；0为网起点，1为网终点；节点数为0...n-1; 
	int i, j;
	int a, b;
	int ok;
	int min, tem;
	while(1){
		flag ++;
		ok = 0;
		str[1].ind = s;          //BFS存时从1号开始
		str[1].prt = s;
		mark[s] = flag;
		top = 2;
		for(i = 1; i < top && !ok; i++){                            //BFS寻找增广路经 
			a = str[i].ind;
			for(j = 1; j < n; j++) if(mark[j] != flag){
				if(flow[a][j].tem < flow[a][j].max){
					str[top].ind = j;
					str[top++].prt = i;
					mark[j] = flag;
					if(j == t){
						ok = 1;
						break;
					}
				}
				else if(flow[j][a].tem > 0){
					str[top].ind = j;
					str[top++].prt = -i;
					mark[j] = flag;
					if(j == t){                        //遇终点跳出； 
						ok = 1;
						break;
					}
				}
			}
		} 
		if(!ok) return;                                            // 判断是否找到可增广路经； 
		a = top - 1; b = str[top-1].prt;
		min = Max;
		while(str[a].ind != s){                                    //算出最大可增量 min； 
			if(b < 0){
				b = -b;
				tem = flow[str[a].ind][str[b].ind].tem;
			}
			else tem = flow[str[b].ind][str[a].ind].max - flow[str[b].ind][str[a].ind].tem;
			if(tem < min) min = tem;
			a = b; b = str[a].prt;
		}
		a = top - 1; b = str[top-1].prt;
		while(str[a].ind != s){                                    //更新路经； 
			if(b < 0){
				b = -b;
				flow[str[a].ind][str[b].ind].tem -= min;
			}
			else flow[str[b].ind][str[a].ind].tem += min;
			a = b; b = str[a].prt;
		}
	}
}
void fill_flow(){
	int i, j;
	scanf("%d", &n);                                                  //n为节点数；
	scanf("%d%d", &s, &t);                                            //读入起点终点； 
	for(i = 0; i < n; i++) for(j = 0; j < n; j++)
		scanf("%d", &flow[i][j].max);                             //读入流矩阵; 
}
int main(){
	int i, j;
	int max_f;
	fill_flow();                                                      //读入；
	max_flow();                                                       //增广 ;
	max_f = 0;
	for(i = 0; i < n; i++) max_f += flow[i][t].tem;
	printf("The max flow is: %d\n", max_f);                           //输出最大流; 
	return 0;
}