算法学习：二分图最大匹配-匈牙利算法

思想：先到先得，能让则让

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

vector<int> evens, odds;

vector<int> odd2even;
vector<bool> oddmatched;

// 此函数可任意改写，或通过临接矩阵记录二分图的边再在此查询
bool can_match(int x, int y) {
    x += y;
    if(x==1) return false;
    int bound = sqrt(x);
    for(int i=2; i<=bound; i++) {
        if(x % i == 0) return false;
    }
    return true;
}

bool match(int evenIdx) {
    for (int oddIdx=0; oddIdx<odds.size(); oddIdx++) {
        if(oddmatched[oddIdx]) continue;
        if(can_match(evens[evenIdx], odds[oddIdx])) {
            oddmatched[oddIdx] = true;
            if(odd2even[oddIdx]==-1 || match(odd2even[oddIdx])) {
                odd2even[oddIdx] = evenIdx;
                return true;
            }
        }
    }
    return false;
}

int main() {
    int n; cin>>n;
    for(int i=0; i<n; i++) {
        int x; cin>>x;
        if(x%2==0) {
            evens.push_back(x);
        } else {
            odds.push_back(x);
        }
    }
    oddmatched.resize(odds.size(), false);
    odd2even.resize(odds.size(), -1); 
    int ans=0;
    for(int i=0; i<evens.size(); i++) {
        fill(oddmatched.begin(), oddmatched.end(), false); // 注意：已匹配标志仅供当次使用，每次发起下一个元素的匹配都要重置，考虑为什么？
        if (match(i)) {
            ans++;
        }
    }
    cout << ans;
}
// 64 位输出请用 printf("%lld")

Donate