| Matrix67's profileMatrix67's SpaceBlogLists | Help |
|
September 27 二分图最大匹配问题匈牙利算法 研究了几个小时,终于明白了。说穿了,就是你从二分图中找出一条路径来,让路径的起点和终点都是还没有匹配过的点,并且路径经过的连线是一条没被匹配、一条已经匹配过,再下一条又没匹配这样交替地出现。找到这样的路径后,显然路径里没被匹配的连线比已经匹配了的连线多一条,于是修改匹配图,把路径里所有匹配过的连线去掉匹配关系,把没有匹配的连线变成匹配的,这样匹配数就比原来多1个。不断执行上述操作,直到找不到这样的路径为止。 TrackbacksThe trackback URL for this entry is: http://matrix-67.spaces.live.com/blog/cns!420B543611BA4E21!201.trak Weblogs that reference this entry
|
|
|