生活随笔
收集整理的這篇文章主要介紹了
二分图匹配问题
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
最大匹配
N對人兩兩之間存在關(guān)系，求最多的匹配
最小點(diǎn)覆蓋＝最大匹配 最大獨(dú)立集＝頂點(diǎn)數(shù)－最大匹配 最小路徑覆蓋＝頂點(diǎn)數(shù)－最大匹配n3，nm{n^3}， {nm} n 3 ， n m n2，n+m{n^2，n+m} n 2 ， n + m int g
[ maxn
] [ maxn
] ;
int girl
[ maxn
] , used
[ maxn
] ;
int find
( int x
) { for ( int i
= 1 ; i
<= n
; ++ i
) { if ( g
[ x
] [ i
] && used
[ i
] == 0 ) { used
[ i
] = 1 ; if ( ! girl
[ i
] || find ( girl
[ i
] ) ) { girl
[ i
] = x
; return true ; } } } return false ;
}
for ( int i
= 1 ; i
<= n
; ++ i
) { mem ( used
, 0 ) ; ans
+ = find ( i
) ;
}
最佳匹配
最佳匹配是完備匹配，每個人都要被匹配。在完備匹配的基礎(chǔ)上求一種權(quán)值最大的匹配
KM算法 ：設(shè)置兩個頂標(biāo)（左邊頂點(diǎn)賦值為對應(yīng)邊的最大權(quán)值，右邊賦值為0）先按照最大的權(quán)值選邊（匈牙利算法），選邊沖突時計算增廣路上最小的降低費(fèi)用，更新每個點(diǎn)（增廣路上左邊的點(diǎn)減去費(fèi)用，右邊的點(diǎn)加上費(fèi)用）這樣保證增廣路可以繼續(xù)找到解而且之前連接的邊也存在，這樣遍歷每個點(diǎn)即可。如果求權(quán)值和最小 的最佳匹配，存負(fù)邊即可。 如果不是完全圖，計算的時候可以將沒有給出的邊賦值為**-inf**這樣不會影響答案，統(tǒng)計答案的時候判定一下即可。 int n
;
int usex
[ maxn
] , usey
[ maxn
] , topx
[ maxn
] , topy
[ maxn
] , slack
[ maxn
] ;
int girl
[ maxn
] , g
[ maxn
] [ maxn
] ;
int dfs ( int x
) { usex
[ x
] = 1 ; for ( int i
= 1 ; i
<= n
; ++ i
) { if ( usey
[ i
] ) continue ; int tmp
= topx
[ x
] + topy
[ i
] - g
[ x
] [ i
] ; if ( tmp
!= 0 ) { slack
[ i
] = min ( tmp
, slack
[ i
] ) ; } else { usey
[ i
] = 1 ; if ( girl
[ i
] == - 1 || dfs ( girl
[ i
] ) ) { girl
[ i
] = x
; return 1 ; } } } return 0 ;
}
int km ( ) { memset ( girl
, - 1 , sizeof ( girl
) ) ; memset ( topx
, 0 , sizeof ( topx
) ) ; memset ( topy
, 0 , sizeof ( topy
) ) ; for ( int i
= 1 ; i
<= n
; ++ i
) { for ( int j
= 1 ; j
<= n
; ++ j
) { topx
[ i
] = max ( topx
[ i
] , g
[ i
] [ j
] ) ; } } for ( int i
= 1 ; i
<= n
; ++ i
) { memset ( slack
, inf
, sizeof ( slack
) ) ; while ( 1 ) { memset ( usex
, 0 , sizeof ( usex
) ) ; memset ( usey
, 0 , sizeof ( usey
) ) ; if ( dfs ( i
) ) break ; int tmp
= inf
; for ( int j
= 1 ; j
<= n
; ++ j
) { if ( usey
[ j
] ) continue ; tmp
= min ( tmp
, slack
[ j
] ) ; } if ( tmp
== inf
) return - 1 ; for ( int j
= 1 ; j
<= n
; ++ j
) { if ( usex
[ j
] ) topx
[ j
] - = tmp
; } for ( int j
= 1 ; j
<= n
; ++ j
) { if ( usey
[ j
] ) topy
[ j
] + = tmp
; else slack
[ j
] - = tmp
; } } } int ans
= 0 ; for ( int i
= 1 ; i
<= n
; ++ i
) { if ( girl
[ i
] != - 1 ) ans
+ = g
[ girl
[ i
] ] [ i
] ; } return ans
;
}
總結(jié)
以上是生活随笔 為你收集整理的二分图匹配问题 的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔 網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔 推薦給好友。
