算法：單身男女問題的科學(xué)解決方案
于是對女2號發(fā)起了進(jìn)攻。
判斷方法：染色法
開始對任意一未染色的頂點(diǎn)染色 判斷其相鄰的頂點(diǎn)中，若未染色則將其染上和相鄰頂點(diǎn)不同的顏色； 若已經(jīng)染色且顏色和相鄰頂點(diǎn)的顏色相同則說明不是二分圖，若顏色不同則繼續(xù)判斷
在二分圖G的子圖M中，M的邊集E中的任意兩條邊都不依附于同一個(gè)頂點(diǎn)，則稱M是一個(gè)匹配。
匹配M的邊集所關(guān)聯(lián)的點(diǎn)為飽和點(diǎn)，否則為非飽和點(diǎn)。如上圖：
的飽和點(diǎn)：。 的飽和點(diǎn)：。
定義：圖G的一條路徑，且路徑中的邊在屬于M和不屬于M中交替出現(xiàn)。
定義：一條交錯(cuò)路，且該交錯(cuò)路的起點(diǎn)和終點(diǎn)都為匹配M的非飽和點(diǎn)。
如上圖，交錯(cuò)路1是增廣路；交錯(cuò)路2不是增廣路，因?yàn)榻K點(diǎn)不是非飽和點(diǎn)。
路徑的邊數(shù)為奇數(shù)，第一條邊和最后一條邊都不屬于M 將路徑中的邊的匹配方式取反操作，會(huì)得到更大的匹配M'，匹配數(shù)加1 M為圖G的最大匹配等價(jià)于不存在M的增廣路
1) 初始匹配M為空 2) 找出一條增廣路徑p，取反操作得到更大的匹配M'代替M 3) 重復(fù)步驟2)，直到找不出增廣路為止
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;
}
輸入
5 5
2 2 5
3 2 3 4
2 1 5
3 1 2 5
1 2
輸出
4
評論
圖片
表情