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