算法概论实验十三

发表于 | 分类于 
1
2
3
4
5
6
7
8
9
10
实验十三

实验目的与要求：
（1）	理解与掌握求解最大流与最小割的基本算法。
（2）	学会应用最大流与最小割算法解决实际问题。


1. 设计与实现项目选择（Project Selection）问题的算法。

2. 设计与实现调查设计（Survey Design）问题的算法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include "stdio.h" 
#include "iostream.h" 
#define Maxint 10000 
#define CLength 7 

template<class Type> 

Type min(Type a,Type b) 
{ 	
	return a<b?a:b; 
} 
int isnull(int mlist[],int n) 
{ 
	for (int j = 1; j <= n;  j++) 
		if (mlist[j]>0) 
			return j;  
		return 0; 
} 
void MaxFlowFF(int n,int Curf[CLength][CLength]) 
{
	//输出流Curf  
	int i,j,tf=0; 
	for (i = 1; i <= n;  i++) 
		for (j = 1; j <= n;  j++) 
			if (Curf[i][j]!=0) 
			{ 
				
				cout<<"顶点"<<i<<"-->"<<"顶点"<<j<<"流量:"<<Curf[i][j]<<"\n"; 
				if (i==1) 
					tf+=Curf[i][j]; 
			} 
			printf("\n当前总流量为:%d\n\n",tf); 
} 
void FordFulkerson(int n,int Cap[CLength][CLength],int Curf[CLength][CLength]) 
{ 
	// s=1,t=n 
	// cap :弧邻接距阵及容量 u(i,j) 
	// Curf:当前流量x(i,j) 
	// maxf:增广路中间变量（节点当前流量）
	// prev:增广路的前导节点
	// LIST:可能增广节点
	
	int i,j; 
	int maxf[CLength]={Maxint},prev[CLength]={0}; 
	int LIST[CLength]={0},Cut[CLength]={0}; 
	maxf[n]=1; 
	bool aug=true; 
	while(maxf[n]>0) // maxf[n]表示得到最大流
	{ 
		// step 2 
		// 取消所有节点标号
		for (j = 1; j <= n;  j++) 
		{ 
			maxf[j]=0; 
			prev[j]=0; 
			LIST[j]=0; 
		} 
		LIST[1]=1; 
		maxf[1]=Maxint; 
		int temp; 
		while(true) 
		{ 
			//step 3 
			// 判断LIST是否非空,非空返回第一个非空值,空则返回0 
			temp=isnull(LIST,n); 
			// LIST非空且maxf[n]==0 
			if(temp!=0 && maxf[n]==0) 
			{ 
				// step 4 
				// LIST中移走temp，并寻找从temp出发的可能增广弧 
				LIST[temp]=0; 
				for(int k = 1; k <= n;  k++) 
				{ 
					// 非饱和前向弧
					if(Curf[temp][k]<Cap[temp][k] && prev[k]==0)// 
					{ 
						maxf[k]=min(maxf[temp],Cap[temp][k]-Curf[temp][k]); 
						prev[k]=temp; 
						LIST[k]=1; 
					} 
					else if(Curf[k][temp]>0 && prev[k]==0) //非空反向弧
					{ 
						maxf[k]=min(maxf[temp],Curf[k][temp]); 
						prev[k]=temp; 
						LIST[k]=1; 
					} 
				} 
				
			} 
			else 
			{ 
				// step 3a,3b 
				if(maxf[n]>0) // 找到了一条增广路
				{ 
					// 对增广当前流Curf 
					int pv=n;
					while(pv!=1) 
					{ 
						// 非饱和前向弧
						if(Curf[prev[pv]][pv]<Cap[prev[pv]][pv]) 
							Curf[prev[pv]][pv]+=maxf[n]; 
						else if(Curf[pv][prev[pv]]>0) //非空反向弧
							Curf[pv][prev[pv]]-=maxf[n]; 
						pv=prev[pv]; 
					} 
					MaxFlowFF(n,Curf); 
				} 
				break; 
			} 
		} // end of while 2 
	} 
	// end of while 1 
} 
void main(void) 
{ 
	int Cap[CLength][CLength]={ 
		{0,0,0,0,0,0,0}, 
		{0,0,3,3,2,0,0}, 
		{0,0,0,0,0,4,0}, 
		{0,0,0,0,1,0,2}, 
		{0,0,1,0,0,0,2}, 
		{0,0,0,0,1,0,1}, 
		{0,0,0,0,0,0,0}, 
	}; 
	int Cf[CLength][CLength]={0}; 
	int i,j; 
	int n=CLength-1; 
	FordFulkerson(n,Cap,Cf); 
	MaxFlowFF(n,Cf); 
}