求kM算法和匈牙利算法的程序代码
kM算法和匈牙利算法的程序代码，最好是用matlab给出的，用c语言亦可。不要用其他的编程语言。
//二分图最佳匹配,kuhn munkras算法,邻接阵形式,复杂度O(m*m*n)
//返回最佳匹配值,传入二分图大小m,n和邻接阵mat,表示权值
//match1,match2返回一个最佳匹配,未匹配顶点match值为-1
//一定注意m
//最小权匹配可将权值取相反数
#include
#define MAXN 310
#define inf 1000000000
#define _clr(x) memset(x,0xff,sizeof(int)*n)
int kuhn_munkras(int m,int n,int mat[][MAXN],int* match1,int* match2){ int s[MAXN],t[MAXN],l1[MAXN],l2[MAXN],p,q,ret=0,i,j,k;
for (i=0;i
for (l1[i]=-inf,j=0;j
l1[i]=mat[i][j]>l1[i]?mat[i][j]:l1[i];
for (i=0;i
for (_clr(match1),_clr(match2),i=0;i
for (_clr(t),s[p=q=0]=i;p
for (k=s[p],j=0;j
if (l1[k]+l2[j]==mat[k][j]&&t[j]
s[++q]=match2[j],t[j]=k;
if (s[q]
for (p=j;p>=0;j=p)
match2[j]=k=t[j],p=match1[k],match1[k]=j;
}
if (match1[i]
for (i--,p=inf,k=0;k
for (j=0;j
if (t[j]
p=l1[s[k]]+l2[j]-mat[s[k]][j];
for (j=0;j
for (k=0;k
}
}
for (i=0;i
ret+=mat[i][match1[i]];
return ret;
}
昨天帮一个同学完成了他的毕业论文上的指派问题的匈牙利算法程序。以前他们跟我讲那算法的时候，他们就没讲清楚。现在回想起来他们说的匈牙利算法都是不完 全正确的。因此以前我就在网上随便帮他们找了一个程序，可是发现那程序25行矩阵就会出问题，运行相当长时间，因为那不是用匈牙利算法解决的。 他们现在被老师逼了，一定要把结果弄出来，没办法了，我也只好认真看了一下匈牙利算法原理。最后选择了Excel的后台VBA 程序来解决。通过一天的努力，这个匈牙利算法已经弄出来了。下面就给出全部的代码。
Java代码
1. '=========================================
2. '作者：大漠.jxzhoumin
3. '=========================================
4.
5. Option Base 1
6. Public r As Integer
7. Public row_gou() As Integer
8. Public col_gou() As Integer
9. Public gou_min_num As Double
10.'=================================================
11.Public Function tj(lb) As Integer
12. Dim k As Integer
13. k = 2
14. Do
15. Set myR = Sheets(lb).Cells(k, 1)
16. If Trim(myR.Value) = "" Then '出现空记录
17. Exit Do
18. End If
19. k = k + 1
20. Loop Until False
21. tj = k - 1
22.End Function
23.'================================================
24.Private Sub CommandButton1_Click()
25.Application.ScreenUpdating = False
26. Call findmin
27.Application.ScreenUpdating = True
28.Worksheets("sheet1").Activate
29.End Sub
30.Sub findmin()
31.Dim num As Double, min_num As Double
32.r = tj("原始数据")
33.Call copy_data
34.With Worksheets("sheet1")
35.For i = 2 To r
36. num = 1000
37. For j = 2 To r
38. If .Cells(i, j).Value
39. min_num = .Cells(i, j).Value
40. num = min_num '获得该行的最小数
41. End If
42. Next j
43. For j = 2 To r
44. .Cells(i, j).Value = .Cells(i, j).Value - min_num '将每行减该行最小数
45. Next j
46.Next i
47.'======================================================================================
48.For i = 2 To r
49. num = 1000
50. For j = 2 To r
51. If .Cells(j, i).Value
52. min_num = .Cells(j, i).Value
53. num = min_num '获得该列的最小数
54. End If
55. Next j
56. For j = 2 To r
57. .Cells(j, i).Value = .Cells(j, i).Value - min_num '将每列减该列最小数
58. Next j
59.Next i
60.End With
61.Call find_draw_zero
62.End Sub
63.Function find_draw_zero()
64.Dim zero_row As Integer
65.zero_row = 0
66.zero_row = findzero()
67.While zero_row > 0
68. Call draw_zero(zero_row)
69. zero_row = findzero()
70.Wend
71.Call bestvalue
72.End Function
73.Function findzero() As Integer
74.Dim zero_num As Integer, zero_row, zero_col As Integer, min_num As Integer
75.zero_num = 0 '行，列0元素的个数
76.min_num = 1000
77.zero_row = 0
78.zero_col = 0
79.With Worksheets("sheet1")
80.For i = 2 To r
81. zero_num = 0
82. For j = 2 To r
83. If .Cells(i, j).Value = 0 Then
84. zero_num = zero_num + 1
85. End If
86. Next j
87. If zero_num 0 And zero_num
88. min_num = zero_num
89. zero_row = i
90. End If
91.Next i
92.End With
93.If min_num = 1000 Then
94. zero_row = 0
95.End If
96.findzero = zero_row
97.End Function
98.Sub draw_zero(zero_row As Integer)
99.Dim zero_col As Integer, i As Integer
100. zero_col = find_col_num(zero_row)
101. With Worksheets("sheet1")
102. .Cells(zero_row, zero_col).Value = "@" '将对应的0划成@
103. For i = 2 To r
104. If .Cells(zero_row, i).Value = 0 Then
105. .Cells(zero_row, i).Value = "*" '找到对应的行的0划成*
106. End If
107. Next i
108. For i = 2 To r
109. If .Cells(i, zero_col).Value = 0 Then
110. .Cells(i, zero_col).Value = "*" '找到对应的列的0划成*
111. End If
112. Next i
113. End With
114. End Sub
115. Function find_col_num(zero_row As Integer) As Integer 116. Dim count As Integer, col_num As Integer, min_count As Integer
117. min_count = 1000
118. With Worksheets("sheet1")
119. For i = 2 To r
120. If .Cells(zero_row, i).Value = 0 Then 121. count = 0
122. For j = 2 To r
123. If .Cells(j, i).Value = 0 Or .Cells(j, i).Value = "*" Then
124. count = count + 1
125. End If
126. Next j
127. If count
128. min_count = count
129. find_col_num = i '找到需要标记的0列的数值，该0的列的0的个数最少
130. End If
131. End If
132. Next i
133. End With
134. End Function
135. Function bestvalue() As Boolean
136. Dim count As Integer
137. count = 0
138. With Worksheets("sheet1")
139. For i = 2 To r
140. For j = 2 To r
141. If .Cells(i, j).Value = "@" Then
142. count = count + 1
143. End If
144. Next j
145. Next i
146. End With
147. If count = r - 1 Then
148. bestvalue = True
149. Call show_infor
150. MsgBox "达到最优解！"
151. Else
152. bestvalue = False
153. Call draw_gou
154. Call find_gou_min_num
155. Call row_gou_jian
156. Call col_gou_jia
157. Call init_second
158. End If
159. End Function
160. Sub draw_gou()
161. Dim i As Integer, count As Integer
162. Dim row_num, col_num As Integer
163. i = 1
164. Erase row_gou
165. Erase col_gou
166. ReDim row_gou(1)
167. ReDim col_gou(1)
168. With Worksheets("sheet1")
169. For i = 2 To r
170. count = 0
171. For j = 2 To r
172. If .Cells(i, j).Value = "@" Then
173. count = count + 1
174. End If
175. Next j
176. If count = 0 Then
177. row_num = i
178. If row_gou(0) = 0 Then
179. row_u = 0
180. Else
181. row_u = UBound(row_gou)
182. End If
183. If col_gou(0) = 0 Then
184. col_u = 0
185. Else
186. col_u = UBound(col_gou)
187. End If
188.
189. For j = 2 To r
190. If .Cells(row_num, j).Value = "*" Then 191. col_num = j
192. End If
193. Next j
194.
195. If chongfu_row(row_num) Then
196. ReDim Preserve row_gou(row_u + 1)
197. row_gou(row_u + 1) = row_num '将行画钩的序列值做标记
198. End If
199. If chongfu_col(col_num) Then
200. ReDim Preserve col_gou(col_u + 1)
201. col_gou(col_u + 1) = col_num '将列画钩的序列值做标记
202. Call col_to_row(col_num)
203. End If
204. End If
205. Next i
206. End With
207. End Sub
208. Function chongfu_row(ByVal row_num As Integer) As Boolean
209. row_u = UBound(row_gou)
210. chongfu_row = True
211. For i = 1 To row_u
212. If row_gou(i) = row_num Then
213. chongfu_row = False
214. End If
215. Next i
216. End Function
217. Function chongfu_col(ByVal col_num As Integer) As Boolean
218. col_u = UBound(col_gou)
219. chongfu_col = True
220. For i = 1 To col_u
221. If col_gou(i) = col_num Then
222. chongfu_col = False
223. End If
224. Next i
225. End Function
226. Sub col_to_row(ByVal col_num As Integer)
227. row_u = UBound(row_gou)
228. col_u = UBound(col_gou)
229. row_num = 0
230. With Worksheets("sheet1")
231. For i = 2 To r
232. If .Cells(i, col_num).Value = "@" Then
233. row_num = i
234. If chongfu_row(row_num) Then
235. ReDim Preserve row_gou(row_u + 1)
236. row_gou(row_u + 1) = row_num '将行画钩的序列值做标记
237. End If
238. For j = 2 To r
239. If .Cells(row_num, i).Value = "*" Then 240. If chongfu_col(col_num) Then
241. ReDim Preserve col_gou(col_u + 1) 242. col_gou(col_u + 1) = i '将列画钩的序列值做标记
243. 'Call col_to_row(i) '全套循环函数得出画钩的行
244. End If
245. End If
246. Next j
247. End If
248. Next i
249. End With
250. End Sub
251. Sub find_gou_min_num()
252. Dim row_u As Integer, row_num As Integer, min_num As Double
253. min_num = 1000
254. row_u = UBound(row_gou)
255. With Worksheets("sheet1")
256. For i = 1 To row_u
257. For j = 2 To r
258. row_num = row_gou(i)
259. If .Cells(row_num, j).Value "*" And .Cells(row_num, j).Value "@" Then
260. If .Cells(row_num, j).Value
263. End If
264. End If
265. Next j
266. Next i
267. End With
268. End Sub
269. Sub row_gou_jian()
270. Dim row_u As Integer, row_num As Integer
271. row_u = UBound(row_gou)
272. With Worksheets("sheet1")
273. For i = 1 To row_u
274. For j = 2 To r
275. row_num = row_gou(i)
276. If .Cells(row_num, j).Value "*" And .Cells(row_num, j).Value "@" Then
277. .Cells(row_num, j).Value = .Cells(row_num, j) - gou_min_num '将画钩的行的数减去最小数
278. End If
279. Next j
280. Next i
281. End With
282. End Sub
283. Sub col_gou_jia()
284. Dim col_u As Integer, col_num As Integer
285. col_u = UBound(col_gou)
286. With Worksheets("sheet1")
287. For i = 1 To col_u
288. col_num = col_gou(i)
289. For j = 2 To r
290. If .Cells(j, col_num).Value "*" And .Cells(j, col_num).Value "@" Then
291. .Cells(j, col_num).Value = Val(Trim(.Cells(j, col_num).Value)) + gou_min_num '将画钩的行的数减去最小数 292. End If 293. Next j 294. Next i 295. End With 296. End Sub
297. Sub init_second()
298. With Worksheets("sheet1") 299. For i = 2 To r 300. For j = 2 To r
301. If .Cells(i, j).Value = "@" Or .Cells(i, j).Value = "*" Then
302. .Cells(i, j).Value = 0 303. End If 304. Next j 305. Next i 306. End With
307. Call find_draw_zero 308. End Sub
309. Sub show_infor()
310. With Worksheets("sheet1") 311. For i = 2 To r
312. For j = 2 To r
313. If .Cells(i, j).Value = "@" Then 314. .Cells(i, j).Value = 1 315. Else: .Cells(i, j).Value = 0 316. End If 317. Next j 318. Next i 319. End With 320. End Sub
321. Sub copy_data() 322. For i = 1 To r
323. For j = 1 To r
324. With Worksheets("原始数据") 325. num = .Cells(i, j).Value 326. End With
327. With Worksheets("sheet1") 328. .Cells(i, j).Value = num 329. End With 330. Next j
331. 332.
Next i End Sub
对匈牙利算法的改进及其应用实例
焦 吉 成
(济南钢铁集团总公司技术中心,山东 济南 250014)
摘 要：本文指出了匈牙利算法存在的缺陷,对其进行了改进,并给出该算法在生产实际中的应用实例。
关键词：匈牙利算法;运筹学；效益矩阵
中图分类号：TP301.6 文献标识码：A 文章编号：1004-4620(2000)02-0055-02
Improving Hungary Algorithm and Its Application
JIAO Ji cheng
(The Technical Center of Jinan Iron and Steel Group,Jinan 250014,China)
Abstract：In this paper,the fault of hungary algorithm is found and corrected.An example also is presented.
Keywords：hungary algorithm;operational research,profit matrix
1 问题的提出
在使用运筹学中旅行推销员模型的算法求解某企业轧钢换辊最优秩序时,我们运用参考文献所提供的算法程序求解该问题,遇到在匈牙利算法子程序中出现死循环现象。经研究发现,文献〔1〕提供的匈牙利算法存在缺陷,从而遗漏了最优分配方案。因此,必须对匈牙利算法进行改进。否则,会影响匈牙利算法在实践中的应用。
2 匈牙利算法
〔2〕
匈牙利算法的基本思想是修改效益矩阵的行 或列,使得每一行或列中至少有一个为零的元素,经过修正后,直至在不同行、不同列中至少有一个零元素,从而得到与这些零元素相对应的一个完全分配方案。当 它用于效益矩阵时,这个完全分配方案就是一个最优分配,它使总的效益为最小。这种方法总是在有限步内收敛于一个最优解。该方法的理论基础是:在效益矩阵的 任何行或列中,加上或减去一个常数后不会改变最优分配。其求解步骤如下:
第一步,修正效益矩阵,使之变成每一行和每一列至少有一个零元素的缩减矩阵:(1)从效益矩阵的每一行元素减去各该行中最小元素;(2)再从所得缩减矩阵的每列减去各该列的最小元素。
第二步,试制一个完全分配方案,它对应于不同行不同列只有一个零元素的缩减矩阵,以求得最优解:(1)如果得到分布在不同行不同列的N个零元素,那么就完成了求最优解的过程。结束。(2)如果所分布于不同行不同列中的零元素不够N个,则转下步。
第三步,作出覆盖所有零元素的最少数量的 直线集合:(1)标记没有完成分配的行。(2)标记已标记行上所有未分配零元素所对应的列。(3)对标记的列中,已完成分配的行进行标记。(4)重复 (2)、(3)直到没有可标记的零元素。(5)对未标记的行和已标记的列画纵、横线,这就得到能覆盖所有零元素的最少数量的直线集合。
第四步,修改缩减矩阵,以达到每行每列至 少有一个零元素的目的:(1)在没有直线覆盖的部分中找出最小元素。(2)对没有画直线的各元素都减去这个元素。(3)对画了横线和直线交叉处的各元素都 加上这个最小元素。(4)对画了一根直线或横线的各元素保持不变。(5)转第二步。
3 对匈牙利算法的改进
在第二步即试制一个完全分配方案中,常规的办法是首先分配行或列中只有一个零元素的行或列,若所得方案不是一个完全分配方案,且还有未分配的零元素时,则随机选取未标记行或列中的零元素,作为一次分配,其算法的计算机程序见文献〔1〕。 但我们发现,用该算法求解时,出现所得分配方案不是一个完全分配方案,而根据第三步的做法,所画横、纵线覆盖了所有元素的情况。经反复多次探索之后,发现 其原因是该算法在这一步中采用的是随机标注行或列中的零元素,作为一次分配,缺乏科学性,从而遗漏了完全分配方案,使文献〔1〕提 供的算法陷入死循环。我们把这一步的匈牙利算法改进为:选择未标注行或列中,零元素最少的行或列,根据行或列中未标记的零元素所在列或行中零元素的多少, 确定这次分配,即选择列或行中零元素最少的列或行为已分配方案,而不是随机标记。使用经过修改后的匈牙利算法程序,不会出现死循环,可以圆满地解决分配问 题。 4 应用实例
随着市场经济的发展,冶金产品市场由买方 市场变为卖方市场,多品种、小批量,成为企业生产的基本方针。某企业第一小型轧钢厂生产12个型号、规格的圆钢和螺纹钢,使用同一组轧机。造成了企业生产 换辊频繁,因此找出一个最优的换辊秩序,在满足市场需求的同时,使换辊所用的时间最少,对企业的生产经营具有重要现实意义。 所用原始数据见表1。
表1 某企业一小型设备调整时间表 h
表2是经缩减之后的效益矩阵,该效益矩阵若采用文献〔1〕提供匈牙利算法子程序求解,是一个不完全分配方案: 5 4 7 1 0 8 2 11 12 3 6 9
若使用我们的改进算法,则得到一个完全分配方案,其具体过程如下:(见表2)
表2 经缩减后的效益矩阵
注:带*号的零元素者表示已分配的元素；代表已分配的行、列；∞表示不能加工I产品后,转支
加工J产品。
(1)首先分配行或列中只有一个零元素行或列,分配方案为: 5 0 7 0 0 0 0 11 12 0 0 9
(2)计算未标注行、列的零元素(表边数值)。
(3)选择零元素最少的行或列(此例中为第10例)为标注行或列。若出现最少零元素个数相等的情况,可选取其中任意一行或列为标注行或列。
(4)根据该行或列中相应列或行中零元素的个数,确定标注的列或行(此例中是第4行)。 (5)转第二步。
此步的最优分配方案是:5 3 7 10 4 8 2 11 12 1 6 9 ,最短时间是36h,但构成了回路
(1-5-4-10-1),因此不是原问题的最优解。为了说明问题,我们把此步单独提出来,若采用文
献〔1〕的算法,在此步陷入死循环,原问题不可能求得最优解。采用我们的改进的算法,则可
求得原问题的最优解是1-8-11-9-12-2-7-3-6-4-10-5-1,相应的最短时间是37h。 我们
同时求出了该系统设备调整时间的最大值(54h),这样,最长时间与最短时间(37h)之差
是17h,可多生产钢材近500t,若按目前每吨毛利500元计算,每一生产周期中,最长与最短
加工顺序相差效益近25万元。
最小费用最大流
(2010-12-02 10:21:39) 转载
一．Ford和Fulkerson迭加算法.
基本思路：把各条弧上单位流量的费用看成某种长度,用求解最短路问题的方法确定一条自V1至Vn的最短路;在将这条最短路作为可扩充路,用求解最大流问题的方法将其上的流量增至最大可能值;而这条最短路上的流量增加后,其上各条弧的单位流量的费用要重新确定,如此多次迭代,最终得到最小费用最大流. 迭加算法：
1) 给定目标流量F或∞,给定最小费用的初始可行流{fij}=0 2) 若V(f)=F,停止,f为最小费用流;否则转(3).
3) 构造{fij} 相应的新的费用有向图W(fij),在W(fij)寻找Vs到Vt的最小费用有向路P(最短路),沿P增加流f的流量直到F,转(2);若不存在从Vs到Vt的最小费用的有向路P,停止.f就是最小费用最大流. 圈算法：
1) 利用Ford和Fulkson标号算法找出流量为F(
3) 搜索N'(f)中的负费用有向图C(Floyd算法),若没有则停止,否则转(4).
4) 在C上找出最大的循环流,并加到N上去,同时修改N'(F)中C的容量,转(3).
匈牙利算法学习资料（转载）作者：依然
二分图最大匹配的匈牙利算法：
二分图是这样一个图，它的顶点可以分类两个集合X和Y，所有的边关联在两个顶点中，
恰好一个属于集合Ｘ，另一个属于集合Ｙ。
最大匹配： 图中包含边数最多的匹配称为图的最大匹配。
完美匹配： 如果所有点都在匹配边上，称这个最大匹配是完美匹配。
最小覆盖：在一个二分图上用最少的点（x 或 y 集合的都行），让每条连接两个点集的边都至少和其中一个点关联。根据konig定理：二分图的最小顶点覆盖数等于最大匹配数。
最小路径覆盖：用尽量少的不相交简单路径(连着n条边)覆盖有向无环图Ｇ的所有结点，且任何一个顶点有且只有一条路径与之关联；（如果把这些路径中的每条路径从它的起始点走到它的终点，那么恰好可以经过图中的每个顶点一次且仅一次）；解决此类问题可以建立一个二分图模型。把所有顶点i拆成两个：Ｘ结点集中的i和Y结点集中的i',如果有边i->j，则在二分图中引入边 i->j'，设二分图最大匹配为m,则结果就是n-m。
最大独立集问题：在Ｎ个点的图G中选出m个点，使这m个点两两之间没有边(没有某种关系)．求m最大值．如果图Ｇ满足二分图条件，则可以用二分图匹配来做．最大独立集点数 = N - 最大匹配数
二分图最大匹配问题的匈牙利算法：
#include using namespace std; const int Max = 405;
int n, m; // 二分图中x和y中点的数目
int link[Max]; // link[x]记录当前与y节点相连的x的节点。 bool map[Max][Max], vis[Max]; // map[i][j]记录连接x和y的边，如果i和j之间有边则为1，否则为0。
bool dfs(int u){ // dfs实现，u表示现在在寻求匹配y的点x。 for(int i = 1; i
if(link[i] == -1 || dfs(link[i])){ // 条件：点i还没匹配，或者link[i]找到新的匹配。
link[i] = u; return true; } }
return false; }
int MaxMatch(){
int i,num = 0;
memset(link, -1, sizeof(link));
for(i = 1;i
memset(vis, 0, sizeof(vis));
if(bfs(i)) num++;
}
return num; }
算法思想：
算法的思路是不停的找增广轨,并增加匹配的个数,增广轨顾名思义是指一条可以使匹配数变多的路径,在匹配问题中,增广轨的表现形式是一条"交错轨",也就是说这条由图的边组成的路径,它的第一条边是目前还没有参与匹配的,第二条边参与了匹配,第三条边没有..最后一条边没有参与匹配,并且始点和终点还没有被选择过.这样交错进行,显然他有奇数条边.那么对于这样一条路径,我们可以将第一条边改为已匹配,第二条边改为未匹配...以此类推.也就是将所有的边进行"反色",容易发现这样修改以后,匹配仍然是合法的,但是匹配数增加了一对.另外,单独的一条连接两个未匹配点的边显然也是交错轨.可以证明,当不能再找到增广轨时,就得
到了一个最大匹配.这也就是匈牙利算法的思路.
最小费用最大流
(2010-12-02 10:21:39)
转载
一．Ford和Fulkerson迭加算法.
基本思路：把各条弧上单位流量的费用看成某种长度,用求解最短路问题的方法确定一条自V1至Vn的最短路;在将这条最短路作为可扩充路,用求解最大流问题的方法将其上的流量增至最大可能值;而这条最短路上的流量增加后,其上各条弧的单位流量的费用要重新确定,如此多次迭代,最终得到最小费用最大流. 迭加算法：
1) 给定目标流量F或∞,给定最小费用的初始可行流{fij}=0 2) 若V(f)=F,停止,f为最小费用流;否则转(3).
3) 构造{fij} 相应的新的费用有向图W(fij),在W(fij)寻找Vs到Vt的最小费用有向路P(最短路),沿P增加流f的流量直到F,转(2);若不存在从Vs到Vt的最小费用的有向路P,停止.f就是最小费用最大流.
圈算法：
1) 利用Ford和Fulkson标号算法找出流量为F(
3) 搜索N'(f)中的负费用有向图C(Floyd算法),若没有则停止,否则转(4).
4) 在C上找出最大的循环流,并加到N上去,同时修改N'(F)中C的容量,转(3).
网络流学习资料 (转载)作者：依然
网络是一个各条边都有权值和方向的图,网络流是满足以下性质的网络：
1.每一条边拥有一个最大容量c，即该条边可以容纳的最大流量。
2.f是流过该边的实际流量，且总有f
3.每个顶点（源点s和汇点t除外）都有流出的流量等于流入的流量。图中只有一个源点一个汇点，且对于源点来说其流入量为0，对于汇点来说流出量为0，源点的流出量等于汇点的流入量，对于最大流问题既是要找出流入汇点的最大流量值。
网络流的实际应用：运输货物的物流问题，水流问题，匹配问题（最大二分匹配）等。
求最大流的算法：
1.EK算法：
EK算法中涉及的三个关键词：残留网络，增广路径，割。
残留网络，假定我们已经找到了一个可行的流，那么对于每条边如果流量小于容量，则表示该条边有剩余，以流的流量我们也可以看成是反向的残留，得到一个残留网络。
增广路径：在残留网络中如果可以找到一条从源点到汇点的路，即为增广路，我们就可以将流值增加这条增广路上的最小边。
割：把网络分成两部分，一部分包含源点s，另一部分包含汇点t，从源集合到汇集合之间的正向流量之和即为割。网络的割中最小的那个，称之为最小割。
EK算法就是在残留网络中寻找增广路使得流值不断增大，直至达到最大为止。Ek算法由于在寻找增广路时具有盲目性(运用广度优先搜索)，算法效率不高。
2.Dinic算法：
基于EK算法的思想，再从源点到汇点做bfs来寻找路时，对各点标一个层次值表示从源点到该点所需的最小步数，然后在这些层次的基础上再做dfs，dfs的时候只能到其下一层的点，且容量需要比已流流量大，然后重复上述过程即可得到解。步骤如下：
1、初始化流量，计算出剩余图
2、根据剩余图计算层次图。若汇点不在层次图内，则算法结束
3、在层次图内用一次dfs过程增广
4、转步骤2
算法模板：
//时间复杂度O（V^2E)
#include
#define Max 210
int flow[Max][Max], d[Max]; //flow is the network
int sta, end, N; //sta is the sourse ,end is the,N is the number of vector
bool bfs(int s)
{
int front=0,rear=0; int q[Max];
memset(d,-1,sizeof(d)); //d[] is the deep
q[rear++]=s; d[s]=0;
while(front
{
int k=q[front++];
for(int i=0;i
if(flow[k][i]>0&&d[i]==-1){
d[i]=d[k]+1;
q[rear++]=i;
}
}
if(d[end]>=0) return true;
return false;
}
int dinic(int k,int sum) //k is the sourse
{
if(k==end) return sum;
int os=sum;
for(int i=0;i
if(d[i]==d[k]+1&&flow[k][i]>0)
{
int a=dinic(i,min(sum,flow[k][i])); //Deep to the end. flow[k][i]-=a;
flow[i][k]+=a;
sum-=a;
}
return os-sum;
}
int main()
{
int ret=0;
while(bfs(sta))
ret+=dinic(sta,INT_MAX);
printf("%dn",ret);
return 0;
}
最大流最小割定理：一个网络的最小割等于最大流。(网络流运用得好坏的精髓)
问题扩展：
最小费用最大流：在保证最大流的情形下，网络中的边，可能不只有流量还有费用，那么如果我们一方面希望网络拥有最大流，另一方面我们要求费用达到最小，这就是一个费用流的问题了，对于费用流的问题，事实上我们可以这么考虑，首先我们必须要找到的是最大流，另一方面我们需要费用最小，而在找最大流的时候我们总是在寻找增广路来增广，来使得我们能得到一个比现在更大的流，那么另一方面要求费用最小，所以我们可以在寻找增广路的时候找一条费用最小路来增广，而费用我们也可以看成是距离类的东西，也就是这样的话，我们可以用最短路，来找出这样一个最小费用的路来进行增广，而不断增广，即可得到最大流，这样我们就可以得到最小费用最大流。
求kM算法和匈牙利算法的程序代码
kM算法和匈牙利算法的程序代码，最好是用matlab给出的，用c语言亦可。不要用其他的编程语言。
//二分图最佳匹配,kuhn munkras算法,邻接阵形式,复杂度O(m*m*n)
//返回最佳匹配值,传入二分图大小m,n和邻接阵mat,表示权值
//match1,match2返回一个最佳匹配,未匹配顶点match值为-1
//一定注意m
//最小权匹配可将权值取相反数
#include
#define MAXN 310
#define inf 1000000000
#define _clr(x) memset(x,0xff,sizeof(int)*n)
int kuhn_munkras(int m,int n,int mat[][MAXN],int* match1,int* match2){ int s[MAXN],t[MAXN],l1[MAXN],l2[MAXN],p,q,ret=0,i,j,k;
for (i=0;i
for (l1[i]=-inf,j=0;j
l1[i]=mat[i][j]>l1[i]?mat[i][j]:l1[i];
for (i=0;i
for (_clr(match1),_clr(match2),i=0;i
for (_clr(t),s[p=q=0]=i;p
for (k=s[p],j=0;j
if (l1[k]+l2[j]==mat[k][j]&&t[j]
s[++q]=match2[j],t[j]=k;
if (s[q]
for (p=j;p>=0;j=p)
match2[j]=k=t[j],p=match1[k],match1[k]=j;
}
if (match1[i]
for (i--,p=inf,k=0;k
for (j=0;j
if (t[j]
p=l1[s[k]]+l2[j]-mat[s[k]][j];
for (j=0;j
for (k=0;k
}
}
for (i=0;i
ret+=mat[i][match1[i]];
return ret;
}
昨天帮一个同学完成了他的毕业论文上的指派问题的匈牙利算法程序。以前他们跟我讲那算法的时候，他们就没讲清楚。现在回想起来他们说的匈牙利算法都是不完 全正确的。因此以前我就在网上随便帮他们找了一个程序，可是发现那程序25行矩阵就会出问题，运行相当长时间，因为那不是用匈牙利算法解决的。 他们现在被老师逼了，一定要把结果弄出来，没办法了，我也只好认真看了一下匈牙利算法原理。最后选择了Excel的后台VBA 程序来解决。通过一天的努力，这个匈牙利算法已经弄出来了。下面就给出全部的代码。
Java代码
1. '=========================================
2. '作者：大漠.jxzhoumin
3. '=========================================
4.
5. Option Base 1
6. Public r As Integer
7. Public row_gou() As Integer
8. Public col_gou() As Integer
9. Public gou_min_num As Double
10.'=================================================
11.Public Function tj(lb) As Integer
12. Dim k As Integer
13. k = 2
14. Do
15. Set myR = Sheets(lb).Cells(k, 1)
16. If Trim(myR.Value) = "" Then '出现空记录
17. Exit Do
18. End If
19. k = k + 1
20. Loop Until False
21. tj = k - 1
22.End Function
23.'================================================
24.Private Sub CommandButton1_Click()
25.Application.ScreenUpdating = False
26. Call findmin
27.Application.ScreenUpdating = True
28.Worksheets("sheet1").Activate
29.End Sub
30.Sub findmin()
31.Dim num As Double, min_num As Double
32.r = tj("原始数据")
33.Call copy_data
34.With Worksheets("sheet1")
35.For i = 2 To r
36. num = 1000
37. For j = 2 To r
38. If .Cells(i, j).Value
39. min_num = .Cells(i, j).Value
40. num = min_num '获得该行的最小数
41. End If
42. Next j
43. For j = 2 To r
44. .Cells(i, j).Value = .Cells(i, j).Value - min_num '将每行减该行最小数
45. Next j
46.Next i
47.'======================================================================================
48.For i = 2 To r
49. num = 1000
50. For j = 2 To r
51. If .Cells(j, i).Value
52. min_num = .Cells(j, i).Value
53. num = min_num '获得该列的最小数
54. End If
55. Next j
56. For j = 2 To r
57. .Cells(j, i).Value = .Cells(j, i).Value - min_num '将每列减该列最小数
58. Next j
59.Next i
60.End With
61.Call find_draw_zero
62.End Sub
63.Function find_draw_zero()
64.Dim zero_row As Integer
65.zero_row = 0
66.zero_row = findzero()
67.While zero_row > 0
68. Call draw_zero(zero_row)
69. zero_row = findzero()
70.Wend
71.Call bestvalue
72.End Function
73.Function findzero() As Integer
74.Dim zero_num As Integer, zero_row, zero_col As Integer, min_num As Integer
75.zero_num = 0 '行，列0元素的个数
76.min_num = 1000
77.zero_row = 0
78.zero_col = 0
79.With Worksheets("sheet1")
80.For i = 2 To r
81. zero_num = 0
82. For j = 2 To r
83. If .Cells(i, j).Value = 0 Then
84. zero_num = zero_num + 1
85. End If
86. Next j
87. If zero_num 0 And zero_num
88. min_num = zero_num
89. zero_row = i
90. End If
91.Next i
92.End With
93.If min_num = 1000 Then
94. zero_row = 0
95.End If
96.findzero = zero_row
97.End Function
98.Sub draw_zero(zero_row As Integer)
99.Dim zero_col As Integer, i As Integer
100. zero_col = find_col_num(zero_row)
101. With Worksheets("sheet1")
102. .Cells(zero_row, zero_col).Value = "@" '将对应的0划成@
103. For i = 2 To r
104. If .Cells(zero_row, i).Value = 0 Then
105. .Cells(zero_row, i).Value = "*" '找到对应的行的0划成*
106. End If
107. Next i
108. For i = 2 To r
109. If .Cells(i, zero_col).Value = 0 Then
110. .Cells(i, zero_col).Value = "*" '找到对应的列的0划成*
111. End If
112. Next i
113. End With
114. End Sub
115. Function find_col_num(zero_row As Integer) As Integer 116. Dim count As Integer, col_num As Integer, min_count As Integer
117. min_count = 1000
118. With Worksheets("sheet1")
119. For i = 2 To r
120. If .Cells(zero_row, i).Value = 0 Then 121. count = 0
122. For j = 2 To r
123. If .Cells(j, i).Value = 0 Or .Cells(j, i).Value = "*" Then
124. count = count + 1
125. End If
126. Next j
127. If count
128. min_count = count
129. find_col_num = i '找到需要标记的0列的数值，该0的列的0的个数最少
130. End If
131. End If
132. Next i
133. End With
134. End Function
135. Function bestvalue() As Boolean
136. Dim count As Integer
137. count = 0
138. With Worksheets("sheet1")
139. For i = 2 To r
140. For j = 2 To r
141. If .Cells(i, j).Value = "@" Then
142. count = count + 1
143. End If
144. Next j
145. Next i
146. End With
147. If count = r - 1 Then
148. bestvalue = True
149. Call show_infor
150. MsgBox "达到最优解！"
151. Else
152. bestvalue = False
153. Call draw_gou
154. Call find_gou_min_num
155. Call row_gou_jian
156. Call col_gou_jia
157. Call init_second
158. End If
159. End Function
160. Sub draw_gou()
161. Dim i As Integer, count As Integer
162. Dim row_num, col_num As Integer
163. i = 1
164. Erase row_gou
165. Erase col_gou
166. ReDim row_gou(1)
167. ReDim col_gou(1)
168. With Worksheets("sheet1")
169. For i = 2 To r
170. count = 0
171. For j = 2 To r
172. If .Cells(i, j).Value = "@" Then
173. count = count + 1
174. End If
175. Next j
176. If count = 0 Then
177. row_num = i
178. If row_gou(0) = 0 Then
179. row_u = 0
180. Else
181. row_u = UBound(row_gou)
182. End If
183. If col_gou(0) = 0 Then
184. col_u = 0
185. Else
186. col_u = UBound(col_gou)
187. End If
188.
189. For j = 2 To r
190. If .Cells(row_num, j).Value = "*" Then 191. col_num = j
192. End If
193. Next j
194.
195. If chongfu_row(row_num) Then
196. ReDim Preserve row_gou(row_u + 1)
197. row_gou(row_u + 1) = row_num '将行画钩的序列值做标记
198. End If
199. If chongfu_col(col_num) Then
200. ReDim Preserve col_gou(col_u + 1)
201. col_gou(col_u + 1) = col_num '将列画钩的序列值做标记
202. Call col_to_row(col_num)
203. End If
204. End If
205. Next i
206. End With
207. End Sub
208. Function chongfu_row(ByVal row_num As Integer) As Boolean
209. row_u = UBound(row_gou)
210. chongfu_row = True
211. For i = 1 To row_u
212. If row_gou(i) = row_num Then
213. chongfu_row = False
214. End If
215. Next i
216. End Function
217. Function chongfu_col(ByVal col_num As Integer) As Boolean
218. col_u = UBound(col_gou)
219. chongfu_col = True
220. For i = 1 To col_u
221. If col_gou(i) = col_num Then
222. chongfu_col = False
223. End If
224. Next i
225. End Function
226. Sub col_to_row(ByVal col_num As Integer)
227. row_u = UBound(row_gou)
228. col_u = UBound(col_gou)
229. row_num = 0
230. With Worksheets("sheet1")
231. For i = 2 To r
232. If .Cells(i, col_num).Value = "@" Then
233. row_num = i
234. If chongfu_row(row_num) Then
235. ReDim Preserve row_gou(row_u + 1)
236. row_gou(row_u + 1) = row_num '将行画钩的序列值做标记
237. End If
238. For j = 2 To r
239. If .Cells(row_num, i).Value = "*" Then 240. If chongfu_col(col_num) Then
241. ReDim Preserve col_gou(col_u + 1) 242. col_gou(col_u + 1) = i '将列画钩的序列值做标记
243. 'Call col_to_row(i) '全套循环函数得出画钩的行
244. End If
245. End If
246. Next j
247. End If
248. Next i
249. End With
250. End Sub
251. Sub find_gou_min_num()
252. Dim row_u As Integer, row_num As Integer, min_num As Double
253. min_num = 1000
254. row_u = UBound(row_gou)
255. With Worksheets("sheet1")
256. For i = 1 To row_u
257. For j = 2 To r
258. row_num = row_gou(i)
259. If .Cells(row_num, j).Value "*" And .Cells(row_num, j).Value "@" Then
260. If .Cells(row_num, j).Value
263. End If
264. End If
265. Next j
266. Next i
267. End With
268. End Sub
269. Sub row_gou_jian()
270. Dim row_u As Integer, row_num As Integer
271. row_u = UBound(row_gou)
272. With Worksheets("sheet1")
273. For i = 1 To row_u
274. For j = 2 To r
275. row_num = row_gou(i)
276. If .Cells(row_num, j).Value "*" And .Cells(row_num, j).Value "@" Then
277. .Cells(row_num, j).Value = .Cells(row_num, j) - gou_min_num '将画钩的行的数减去最小数
278. End If
279. Next j
280. Next i
281. End With
282. End Sub
283. Sub col_gou_jia()
284. Dim col_u As Integer, col_num As Integer
285. col_u = UBound(col_gou)
286. With Worksheets("sheet1")
287. For i = 1 To col_u
288. col_num = col_gou(i)
289. For j = 2 To r
290. If .Cells(j, col_num).Value "*" And .Cells(j, col_num).Value "@" Then
291. .Cells(j, col_num).Value = Val(Trim(.Cells(j, col_num).Value)) + gou_min_num '将画钩的行的数减去最小数 292. End If 293. Next j 294. Next i 295. End With 296. End Sub
297. Sub init_second()
298. With Worksheets("sheet1") 299. For i = 2 To r 300. For j = 2 To r
301. If .Cells(i, j).Value = "@" Or .Cells(i, j).Value = "*" Then
302. .Cells(i, j).Value = 0 303. End If 304. Next j 305. Next i 306. End With
307. Call find_draw_zero 308. End Sub
309. Sub show_infor()
310. With Worksheets("sheet1") 311. For i = 2 To r
312. For j = 2 To r
313. If .Cells(i, j).Value = "@" Then 314. .Cells(i, j).Value = 1 315. Else: .Cells(i, j).Value = 0 316. End If 317. Next j 318. Next i 319. End With 320. End Sub
321. Sub copy_data() 322. For i = 1 To r
323. For j = 1 To r
324. With Worksheets("原始数据") 325. num = .Cells(i, j).Value 326. End With
327. With Worksheets("sheet1") 328. .Cells(i, j).Value = num 329. End With 330. Next j
331. 332.
Next i End Sub
对匈牙利算法的改进及其应用实例
焦 吉 成
(济南钢铁集团总公司技术中心,山东 济南 250014)
摘 要：本文指出了匈牙利算法存在的缺陷,对其进行了改进,并给出该算法在生产实际中的应用实例。
关键词：匈牙利算法;运筹学；效益矩阵
中图分类号：TP301.6 文献标识码：A 文章编号：1004-4620(2000)02-0055-02
Improving Hungary Algorithm and Its Application
JIAO Ji cheng
(The Technical Center of Jinan Iron and Steel Group,Jinan 250014,China)
Abstract：In this paper,the fault of hungary algorithm is found and corrected.An example also is presented.
Keywords：hungary algorithm;operational research,profit matrix
1 问题的提出
在使用运筹学中旅行推销员模型的算法求解某企业轧钢换辊最优秩序时,我们运用参考文献所提供的算法程序求解该问题,遇到在匈牙利算法子程序中出现死循环现象。经研究发现,文献〔1〕提供的匈牙利算法存在缺陷,从而遗漏了最优分配方案。因此,必须对匈牙利算法进行改进。否则,会影响匈牙利算法在实践中的应用。
2 匈牙利算法
〔2〕
匈牙利算法的基本思想是修改效益矩阵的行 或列,使得每一行或列中至少有一个为零的元素,经过修正后,直至在不同行、不同列中至少有一个零元素,从而得到与这些零元素相对应的一个完全分配方案。当 它用于效益矩阵时,这个完全分配方案就是一个最优分配,它使总的效益为最小。这种方法总是在有限步内收敛于一个最优解。该方法的理论基础是:在效益矩阵的 任何行或列中,加上或减去一个常数后不会改变最优分配。其求解步骤如下:
第一步,修正效益矩阵,使之变成每一行和每一列至少有一个零元素的缩减矩阵:(1)从效益矩阵的每一行元素减去各该行中最小元素;(2)再从所得缩减矩阵的每列减去各该列的最小元素。
第二步,试制一个完全分配方案,它对应于不同行不同列只有一个零元素的缩减矩阵,以求得最优解:(1)如果得到分布在不同行不同列的N个零元素,那么就完成了求最优解的过程。结束。(2)如果所分布于不同行不同列中的零元素不够N个,则转下步。
第三步,作出覆盖所有零元素的最少数量的 直线集合:(1)标记没有完成分配的行。(2)标记已标记行上所有未分配零元素所对应的列。(3)对标记的列中,已完成分配的行进行标记。(4)重复 (2)、(3)直到没有可标记的零元素。(5)对未标记的行和已标记的列画纵、横线,这就得到能覆盖所有零元素的最少数量的直线集合。
第四步,修改缩减矩阵,以达到每行每列至 少有一个零元素的目的:(1)在没有直线覆盖的部分中找出最小元素。(2)对没有画直线的各元素都减去这个元素。(3)对画了横线和直线交叉处的各元素都 加上这个最小元素。(4)对画了一根直线或横线的各元素保持不变。(5)转第二步。
3 对匈牙利算法的改进
在第二步即试制一个完全分配方案中,常规的办法是首先分配行或列中只有一个零元素的行或列,若所得方案不是一个完全分配方案,且还有未分配的零元素时,则随机选取未标记行或列中的零元素,作为一次分配,其算法的计算机程序见文献〔1〕。 但我们发现,用该算法求解时,出现所得分配方案不是一个完全分配方案,而根据第三步的做法,所画横、纵线覆盖了所有元素的情况。经反复多次探索之后,发现 其原因是该算法在这一步中采用的是随机标注行或列中的零元素,作为一次分配,缺乏科学性,从而遗漏了完全分配方案,使文献〔1〕提 供的算法陷入死循环。我们把这一步的匈牙利算法改进为:选择未标注行或列中,零元素最少的行或列,根据行或列中未标记的零元素所在列或行中零元素的多少, 确定这次分配,即选择列或行中零元素最少的列或行为已分配方案,而不是随机标记。使用经过修改后的匈牙利算法程序,不会出现死循环,可以圆满地解决分配问 题。 4 应用实例
随着市场经济的发展,冶金产品市场由买方 市场变为卖方市场,多品种、小批量,成为企业生产的基本方针。某企业第一小型轧钢厂生产12个型号、规格的圆钢和螺纹钢,使用同一组轧机。造成了企业生产 换辊频繁,因此找出一个最优的换辊秩序,在满足市场需求的同时,使换辊所用的时间最少,对企业的生产经营具有重要现实意义。 所用原始数据见表1。
表1 某企业一小型设备调整时间表 h
表2是经缩减之后的效益矩阵,该效益矩阵若采用文献〔1〕提供匈牙利算法子程序求解,是一个不完全分配方案: 5 4 7 1 0 8 2 11 12 3 6 9
若使用我们的改进算法,则得到一个完全分配方案,其具体过程如下:(见表2)
表2 经缩减后的效益矩阵
注:带*号的零元素者表示已分配的元素；代表已分配的行、列；∞表示不能加工I产品后,转支
加工J产品。
(1)首先分配行或列中只有一个零元素行或列,分配方案为: 5 0 7 0 0 0 0 11 12 0 0 9
(2)计算未标注行、列的零元素(表边数值)。
(3)选择零元素最少的行或列(此例中为第10例)为标注行或列。若出现最少零元素个数相等的情况,可选取其中任意一行或列为标注行或列。
(4)根据该行或列中相应列或行中零元素的个数,确定标注的列或行(此例中是第4行)。 (5)转第二步。
此步的最优分配方案是:5 3 7 10 4 8 2 11 12 1 6 9 ,最短时间是36h,但构成了回路
(1-5-4-10-1),因此不是原问题的最优解。为了说明问题,我们把此步单独提出来,若采用文
献〔1〕的算法,在此步陷入死循环,原问题不可能求得最优解。采用我们的改进的算法,则可
求得原问题的最优解是1-8-11-9-12-2-7-3-6-4-10-5-1,相应的最短时间是37h。 我们
同时求出了该系统设备调整时间的最大值(54h),这样,最长时间与最短时间(37h)之差
是17h,可多生产钢材近500t,若按目前每吨毛利500元计算,每一生产周期中,最长与最短
加工顺序相差效益近25万元。
最小费用最大流
(2010-12-02 10:21:39) 转载
一．Ford和Fulkerson迭加算法.
基本思路：把各条弧上单位流量的费用看成某种长度,用求解最短路问题的方法确定一条自V1至Vn的最短路;在将这条最短路作为可扩充路,用求解最大流问题的方法将其上的流量增至最大可能值;而这条最短路上的流量增加后,其上各条弧的单位流量的费用要重新确定,如此多次迭代,最终得到最小费用最大流. 迭加算法：
1) 给定目标流量F或∞,给定最小费用的初始可行流{fij}=0 2) 若V(f)=F,停止,f为最小费用流;否则转(3).
3) 构造{fij} 相应的新的费用有向图W(fij),在W(fij)寻找Vs到Vt的最小费用有向路P(最短路),沿P增加流f的流量直到F,转(2);若不存在从Vs到Vt的最小费用的有向路P,停止.f就是最小费用最大流. 圈算法：
1) 利用Ford和Fulkson标号算法找出流量为F(
3) 搜索N'(f)中的负费用有向图C(Floyd算法),若没有则停止,否则转(4).
4) 在C上找出最大的循环流,并加到N上去,同时修改N'(F)中C的容量,转(3).
匈牙利算法学习资料（转载）作者：依然
二分图最大匹配的匈牙利算法：
二分图是这样一个图，它的顶点可以分类两个集合X和Y，所有的边关联在两个顶点中，
恰好一个属于集合Ｘ，另一个属于集合Ｙ。
最大匹配： 图中包含边数最多的匹配称为图的最大匹配。
完美匹配： 如果所有点都在匹配边上，称这个最大匹配是完美匹配。
最小覆盖：在一个二分图上用最少的点（x 或 y 集合的都行），让每条连接两个点集的边都至少和其中一个点关联。根据konig定理：二分图的最小顶点覆盖数等于最大匹配数。
最小路径覆盖：用尽量少的不相交简单路径(连着n条边)覆盖有向无环图Ｇ的所有结点，且任何一个顶点有且只有一条路径与之关联；（如果把这些路径中的每条路径从它的起始点走到它的终点，那么恰好可以经过图中的每个顶点一次且仅一次）；解决此类问题可以建立一个二分图模型。把所有顶点i拆成两个：Ｘ结点集中的i和Y结点集中的i',如果有边i->j，则在二分图中引入边 i->j'，设二分图最大匹配为m,则结果就是n-m。
最大独立集问题：在Ｎ个点的图G中选出m个点，使这m个点两两之间没有边(没有某种关系)．求m最大值．如果图Ｇ满足二分图条件，则可以用二分图匹配来做．最大独立集点数 = N - 最大匹配数
二分图最大匹配问题的匈牙利算法：
#include using namespace std; const int Max = 405;
int n, m; // 二分图中x和y中点的数目
int link[Max]; // link[x]记录当前与y节点相连的x的节点。 bool map[Max][Max], vis[Max]; // map[i][j]记录连接x和y的边，如果i和j之间有边则为1，否则为0。
bool dfs(int u){ // dfs实现，u表示现在在寻求匹配y的点x。 for(int i = 1; i
if(link[i] == -1 || dfs(link[i])){ // 条件：点i还没匹配，或者link[i]找到新的匹配。
link[i] = u; return true; } }
return false; }
int MaxMatch(){
int i,num = 0;
memset(link, -1, sizeof(link));
for(i = 1;i
memset(vis, 0, sizeof(vis));
if(bfs(i)) num++;
}
return num; }
算法思想：
算法的思路是不停的找增广轨,并增加匹配的个数,增广轨顾名思义是指一条可以使匹配数变多的路径,在匹配问题中,增广轨的表现形式是一条"交错轨",也就是说这条由图的边组成的路径,它的第一条边是目前还没有参与匹配的,第二条边参与了匹配,第三条边没有..最后一条边没有参与匹配,并且始点和终点还没有被选择过.这样交错进行,显然他有奇数条边.那么对于这样一条路径,我们可以将第一条边改为已匹配,第二条边改为未匹配...以此类推.也就是将所有的边进行"反色",容易发现这样修改以后,匹配仍然是合法的,但是匹配数增加了一对.另外,单独的一条连接两个未匹配点的边显然也是交错轨.可以证明,当不能再找到增广轨时,就得
到了一个最大匹配.这也就是匈牙利算法的思路.
最小费用最大流
(2010-12-02 10:21:39)
转载
一．Ford和Fulkerson迭加算法.
基本思路：把各条弧上单位流量的费用看成某种长度,用求解最短路问题的方法确定一条自V1至Vn的最短路;在将这条最短路作为可扩充路,用求解最大流问题的方法将其上的流量增至最大可能值;而这条最短路上的流量增加后,其上各条弧的单位流量的费用要重新确定,如此多次迭代,最终得到最小费用最大流. 迭加算法：
1) 给定目标流量F或∞,给定最小费用的初始可行流{fij}=0 2) 若V(f)=F,停止,f为最小费用流;否则转(3).
3) 构造{fij} 相应的新的费用有向图W(fij),在W(fij)寻找Vs到Vt的最小费用有向路P(最短路),沿P增加流f的流量直到F,转(2);若不存在从Vs到Vt的最小费用的有向路P,停止.f就是最小费用最大流.
圈算法：
1) 利用Ford和Fulkson标号算法找出流量为F(
3) 搜索N'(f)中的负费用有向图C(Floyd算法),若没有则停止,否则转(4).
4) 在C上找出最大的循环流,并加到N上去,同时修改N'(F)中C的容量,转(3).
网络流学习资料 (转载)作者：依然
网络是一个各条边都有权值和方向的图,网络流是满足以下性质的网络：
1.每一条边拥有一个最大容量c，即该条边可以容纳的最大流量。
2.f是流过该边的实际流量，且总有f
3.每个顶点（源点s和汇点t除外）都有流出的流量等于流入的流量。图中只有一个源点一个汇点，且对于源点来说其流入量为0，对于汇点来说流出量为0，源点的流出量等于汇点的流入量，对于最大流问题既是要找出流入汇点的最大流量值。
网络流的实际应用：运输货物的物流问题，水流问题，匹配问题（最大二分匹配）等。
求最大流的算法：
1.EK算法：
EK算法中涉及的三个关键词：残留网络，增广路径，割。
残留网络，假定我们已经找到了一个可行的流，那么对于每条边如果流量小于容量，则表示该条边有剩余，以流的流量我们也可以看成是反向的残留，得到一个残留网络。
增广路径：在残留网络中如果可以找到一条从源点到汇点的路，即为增广路，我们就可以将流值增加这条增广路上的最小边。
割：把网络分成两部分，一部分包含源点s，另一部分包含汇点t，从源集合到汇集合之间的正向流量之和即为割。网络的割中最小的那个，称之为最小割。
EK算法就是在残留网络中寻找增广路使得流值不断增大，直至达到最大为止。Ek算法由于在寻找增广路时具有盲目性(运用广度优先搜索)，算法效率不高。
2.Dinic算法：
基于EK算法的思想，再从源点到汇点做bfs来寻找路时，对各点标一个层次值表示从源点到该点所需的最小步数，然后在这些层次的基础上再做dfs，dfs的时候只能到其下一层的点，且容量需要比已流流量大，然后重复上述过程即可得到解。步骤如下：
1、初始化流量，计算出剩余图
2、根据剩余图计算层次图。若汇点不在层次图内，则算法结束
3、在层次图内用一次dfs过程增广
4、转步骤2
算法模板：
//时间复杂度O（V^2E)
#include
#define Max 210
int flow[Max][Max], d[Max]; //flow is the network
int sta, end, N; //sta is the sourse ,end is the,N is the number of vector
bool bfs(int s)
{
int front=0,rear=0; int q[Max];
memset(d,-1,sizeof(d)); //d[] is the deep
q[rear++]=s; d[s]=0;
while(front
{
int k=q[front++];
for(int i=0;i
if(flow[k][i]>0&&d[i]==-1){
d[i]=d[k]+1;
q[rear++]=i;
}
}
if(d[end]>=0) return true;
return false;
}
int dinic(int k,int sum) //k is the sourse
{
if(k==end) return sum;
int os=sum;
for(int i=0;i
if(d[i]==d[k]+1&&flow[k][i]>0)
{
int a=dinic(i,min(sum,flow[k][i])); //Deep to the end. flow[k][i]-=a;
flow[i][k]+=a;
sum-=a;
}
return os-sum;
}
int main()
{
int ret=0;
while(bfs(sta))
ret+=dinic(sta,INT_MAX);
printf("%dn",ret);
return 0;
}
最大流最小割定理：一个网络的最小割等于最大流。(网络流运用得好坏的精髓)
问题扩展：
最小费用最大流：在保证最大流的情形下，网络中的边，可能不只有流量还有费用，那么如果我们一方面希望网络拥有最大流，另一方面我们要求费用达到最小，这就是一个费用流的问题了，对于费用流的问题，事实上我们可以这么考虑，首先我们必须要找到的是最大流，另一方面我们需要费用最小，而在找最大流的时候我们总是在寻找增广路来增广，来使得我们能得到一个比现在更大的流，那么另一方面要求费用最小，所以我们可以在寻找增广路的时候找一条费用最小路来增广，而费用我们也可以看成是距离类的东西，也就是这样的话，我们可以用最短路，来找出这样一个最小费用的路来进行增广，而不断增广，即可得到最大流，这样我们就可以得到最小费用最大流。