hungarian.cpp (2)

Bài viết này không còn hiệu quả, hãy xem bài viết mới hơn:

https://sites.google.com/site/kc97ble/algorithm-graph/cap-ghep-tren-do-thi-hai-phia-khong-trong-so

Bài toán

Tìm cặp ghép cực đại trên đồ thị hai phía không trọng số.

Độ phức tạp

O(m.n2)

Code này của Nguyễn Tiến Trung Kiên

#include <stdio.h>

#include <vector>

#include <iostream>

#include <algorithm>

using namespace std;

#define f1(i,n) for (int i=1; i<=n; i++)

#define N 202

int n, t;

vector<int> a[N];

int Visited[N];

int Assigned[N];

bool visit(int u){

    Visited[u]=t;

    for (int i=0,v; v=a[u][i]; i++)

    if ( !Assigned[v] || (Visited[Assigned[v]]!=t && visit(Assigned[v])) ) {

        Assigned[v]=u;

        Assigned[u]=v;

        return true;

    }

    return false;

}

void enter(){

    int p, q;

    cin >> p >> q;

    n=max(p,q);

    while (cin >> p >> q){

        a[p].push_back(q+n);

        a[q+n].push_back(p);

    }

    f1(i,2*n) a[i].push_back(0);

}

main(){

    ios :: sync_with_stdio(false);

    enter();

    f1(i,n) if (!Assigned[i]) { t++; visit(i); } // Left-only

    int Answer=0;

    f1(i,n) if (Assigned[i]) Answer++;

    cout << Answer << endl;

    f1(i,n) if (Assigned[i]) cout << i << " " << Assigned[i]-n << endl;

}

Tính chất

Assigned[u]=v và v!=0 thì Assigned[v]=u.

Nhận xét

Code này đã được dùng để nộp cho một bài trên SPOJ.

Tham khảo

vn.spoj.com/problems/MATCH1/