1 婚戀市場咆耿，明碼實價
中國如今男女比例嚴(yán)重失衡德谅，2021年預(yù)計將有9200萬單身貴族爹橱。為了幫助解決這個社會性問題萨螺，提升整體人民的幸福感，小K打算投身到這份偉大的事業(yè)中愧驱。
“幾何思維”婚戀所慰技，用最科學(xué)的方法，幫你脫單组砚。通過概率論尋找最佳匹配對象吻商，再通過微積分精確計算好感上升曲線，最后用數(shù)值分析無限逼近對方的理想型糟红。最可怕的是艾帐，還包郵呢親乌叶，關(guān)注一波了解一下？
上班第一天柒爸，老板給了小K一份單身男女好感的數(shù)據(jù)資料准浴。如下圖，連線表示雙方互有好感捎稚，可以嘗試處對象乐横。
突然遇到了一個問題，那怎么才能進行最大的匹配今野，創(chuàng)造整體人民最大的幸福感呢葡公，當(dāng)然也可以順便拿最多的中介費啦。
2 不要慫条霜，就是干
很多時候不是你比別人差催什，而是你執(zhí)行力不夠，在猶豫中喪失機會宰睡。
大家就先行動起來吧蛆楞。
快看，男1號選手在小K的鼓勵(慫恿)下夹厌，率先對女1號發(fā)起了進攻豹爹。在離失敗只有0.01公分的時候，他竟然奇跡般的完成反殺矛纹，沒錯臂聋，他成功啦，這種高超的技巧或南，嫻熟的手法簡直如同教科書一般孩等，值得在座的每個同學(xué)深入研究反復(fù)琢磨啊。
男2號選手也不甘落后采够，也對女2號選手發(fā)起了進攻肄方，沒錯，又一次成功啦蹬癌。
男3號選手：我勒個去权她，我上我也行啊。于是也對自己心動的女1號發(fā)起了進攻逝薪，毫無意外隅要，他陣亡了。董济。步清。
中間彩蛋。
男3號不甘心，原地復(fù)活廓啊，想再戰(zhàn)一回欢搜。在一個地方跌倒，咱們就換一個地方再跌谴轮。狂巢。。
于是對女2號發(fā)起了進攻书聚。
幾經(jīng)波折唧领。
男3號終于也成為了有牽絆的男人，不論未來有多久雌续，只在乎曾經(jīng)擁有過斩个。
男4一看：這也沒我啥事兒了啊。
以上的過程其實就是經(jīng)典的匈牙利算法驯杜，求解二分圖的最大匹配問題受啥。
3 匈牙利算法
二分圖
定義：設(shè)G=(V,E)是一個無向圖，頂點集V可分割為兩個互不相交的子集X鸽心，Y滚局，并且圖中每條邊關(guān)聯(lián)的兩個頂點都分屬于這兩個互不相交的子集，兩個子集內(nèi)的頂點不相鄰顽频。
判斷是否為二分圖的充要條件：G至少有兩個頂點,且其所有回路的長度均為偶數(shù)藤肢。
判斷方法：染色法
- 開始對任意一未染色的頂點染色
- 判斷其相鄰的頂點中，若未染色則將其染上和相鄰頂點不同的顏色糯景；
- 若已經(jīng)染色且顏色和相鄰頂點的顏色相同則說明不是二分圖嘁圈，若顏色不同則繼續(xù)判斷
可用bfs或者dfs。
匹配
在二分圖G的子圖M中蟀淮，M的邊集E中的任意兩條邊都不依附于同一個頂點最住，則稱M是一個匹配。
飽和點
匹配M的邊集所關(guān)聯(lián)的點為飽和點怠惶，否則為非飽和點涨缚。如上圖：
- M1M1 的飽和點：X1,X3,X4,Y1,Y2,Y3X1,X3,X4,Y1,Y2,Y3。
- M2M2的飽和點：X1,X2,Y1,Y3X1,X2,Y1,Y3策治。
交錯路
定義：圖G的一條路徑脓魏，且路徑中的邊在屬于M和不屬于M中交替出現(xiàn)。
增廣路(非網(wǎng)絡(luò)流中的定義)
定義：一條交錯路览妖，且該交錯路的起點和終點都為匹配M的非飽和點轧拄。
如上圖，交錯路1是增廣路讽膏；交錯路2不是增廣路，因為終點 X1 不是非飽和點拄丰。
由增廣路推出以下結(jié)論：
- 路徑的邊數(shù)為奇數(shù)府树，第一條邊和最后一條邊都不屬于M
- 將路徑中的邊的匹配方式取反操作俐末，會得到更大的匹配M'，匹配數(shù)加1
- M為圖G的最大匹配等價于不存在M的增廣路
匈牙利算法核心思想：
- 1.初始匹配M為空
- 2.找出一條增廣路徑p奄侠，取反操作得到更大的匹配M'代替M
- 3.重復(fù)步驟2卓箫，直到找不出增廣路為止
4 代碼實現(xiàn)
變量定義及初始化
const int MAXM = 200, MAXN = 200;
bool map[MAXN][MAXM] = {false}, visit[MAXM];
int n, m, x[MAXM], y[MAXN], ans = 0;
初始化
void init() {
memset(x, 0xff, MAXM * 4);
memset(y, 0xff, MAXN * 4);
memset(map, false, MAXN * MAXM);
int num, temp;
cin >> n >> m;
for (int i = 0; i < n; ++i) {
cin >> num;
for (int j = 0; j < num; ++j) {
cin >> temp;
map[i][temp - 1] = true;
}
}
}
遞歸尋找增廣路
bool hungary(int u) {
for (int i = 0; i < m; ++i) {
if (!visit[i] && map[u][i]) {
visit[i] = true;
if (y[i] == -1 || hungary(y[i])) {
x[u] = i;
y[i] = u;
return true;
}
}
}
return false;
}
遍歷所有點
int main() {
init();
for (int i = 0; i < n; ++i) {
if (x[i] == -1) {
memset(visit, false, MAXM);
if (hungary(i)) {
ans++;
}
}
}
cout << ans << endl;
return 0;
}
測試數(shù)據(jù)
輸入
5 5
2 2 5
3 2 3 4
2 1 5
3 1 2 5
1 2
輸出
4
作者：幾何思維
原文鏈接：https://www.cnblogs.com/kylewilson/p/14517884.html
