最大二分匹配

Question

目前最著名的最大二分匹配算法是O(√VE)。

下面是我解决上述问题的算法：给定两个集合 S1 和 S2 以及它们之间的 E 边。

第一步：将 S1 和 S2 按度数递增排序

第2步：按排序顺序挑选集合中的元素并将其分配给另一个集合中的下一个空闲元素，计算匹配的数量。

步骤 3：在 S1 上执行步骤 2，然后在 S2 上执行。

第 4 步：取第 3 步的最大值。

这使得算法的复杂度为 O(Vlog(V)+(V+E)).

我无法证明上述算法的正确性，所以任何人都可以帮助我解决上述示例失败的任何反例，因为该算法不适用于 spoj 问题 MATCHING 所以算法是错误的但是想不出反例。

谢谢

#include<bits/stdc++.h>
#define ll long long int
using namespace std;


int main(){

    ll c,b,p;
    cin >> c >> b >> p;
    c+=1;
    b+=1;
    ll mx = max(c,b);
    c =mx;
    b =mx;
    vector<ll> adjcow[c];
    vector<ll> adjbull[b];

    for(ll i=0; i<p; i++){
        ll x,y;
        cin >> x >> y;
        adjcow[x].push_back(y);
        adjbull[y].push_back(x);
    }

    /*
    for(ll i=0; i<c; i++){
        cout << i << " ";
        for(auto x:adjcow[i])
            cout << x << " ";
        cout << "\n";
    }

    for(ll i=0; i<b; i++){
        cout << i << " ";
        for(auto x : adjbull[i])
            cout << x << " ";
        cout << endl; 
    }
    */

    vector<pair<ll, ll>> deg1(c);
    vector<pair<ll, ll>> deg2(b);


    for(ll i=0; i<c; i++){
        ll count = 0;
        for(auto x: adjcow[i])
            count++;
        deg1[i] = {count, i};
    }

    for(ll i=0; i<b; i++){
        ll count = 0;
        for(auto x: adjbull[i])
            count++;
        deg2[i] = {count,i};
    }

    sort(deg1.begin(), deg1.end());
    sort(deg2.begin(), deg2.end());

    vector<bool> isTaken1(c,0);
    vector<bool> isTaken2(b,0);

    /*
    for(ll i=0; i<c; i++)
        cout << deg1[i].first << " " << deg1[i].second  << ", ";

    cout << endl;

    for(ll i=0; i<b; i++) 
        cout << deg2[i].first <<" "<< deg2[i].second  << ", ";

    cout << endl;
    */

    ll ansCow =0;
    for(auto x:deg1){
        ll node = x.second;
        for(auto u: adjcow[node]){
            if(isTaken1[u]==0){
    //          cout << node << "-> " << u << "\n";
                isTaken1[u] = 1;
                ansCow++;
                break;
            }
        }
    }

    //cout << "\n\n";

    ll ansBull =0;
    for(auto x:deg2){
        ll node = x.second;
        for(auto u: adjbull[node]){
            if(isTaken2[u]==0){
    //          cout << node << "->" << u << "\n";
                isTaken2[u] = 1;
                ansBull++;
                break;
            }
        }
    }

    cout << max(ansCow, ansBull) << "\n";
}

输入::

Answer 1

反例如下所示。请注意，每个节点的度数均为 2，因此排序无效。从左往右连接时，如果1选A，2选B，则3不能连接。所以结果是2，从右往左连接的时候，如果A选1，B选2，那么C就不能连接。结果又是2。但是正确结果是3，1接C，2接B，3接A。

程序的输入为：

最大二分匹配

Maximum bipartite matching

algorithm

graph-theory

graph-algorithm