hungarian.cpp

Bài toán

Tìm bộ ghép cực đại trên đồ thị hai phía có trọng số

Độ phức tạp

tối đa lên đến : O(n^4)

Code này của Đỗ Ngọc Khánh

#include <cstdio>

#include <cstring>

#include <ctime>

#include <cstdlib>

#include <algorithm>

#include <vector>

#include <queue>

#include <iostream>

using namespace std;

typedef long long llint;

const int maxN=1000+10,maxQ=maxN*maxN;

typedef pair<int,int> II;

#define fs first

#define sd second

#define MP make_pair

#define PB push_back

#define FORE(it,c) for(typeof(c.begin())it=c.begin();it!=c.end();it++)

int n,m;

llint d[maxN][maxN];

vector<II> a[maxN];

II qu[maxQ];

int top,bot;

bool inq[maxN][maxN];

void solve(){

    memset(d,0x1F,sizeof d);

    scanf("%d%d",&n,&m);

    int u,v,c;

    for (int i=1;i<=n;i++) a[i].clear();

    top=0; bot=1;

    memset(inq,false,sizeof inq);

    for (int i=0;i<m;i++){

        scanf("%d%d%d",&u,&v,&c);

        a[u].PB(MP(v,c));

        d[u][v]=c;

        inq[u][v]=true;

        qu[++top]=MP(u,v);

    }

    //printf("bot=%d,top=%d\n",bot,top);

    while (bot<=top){

        II u=qu[(bot++)%maxQ];

        llint D=d[u.fs][u.sd]; inq[u.fs][u.sd]=false;

        FORE (it,a[u.sd]) if (d[u.fs][it->fs]>D+it->sd){

            d[u.fs][it->fs]=D+it->sd;

            if (!inq[u.fs][it->fs]){

                inq[u.fs][it->fs]=true;

                qu[(++top)%maxQ]=MP(u.fs,it->fs);

            }

        }

    }

    for (int i=1;i<=n;i++){

        if (d[i][i]>=d[0][0]) printf("-1\n");

        else cout<<d[i][i]<<endl;

    }

    fprintf(stderr,"Top=%d\n",top);

}

int main(){

    freopen("tours.inp","r",stdin);

    freopen("tours.out","w",stdout);

    int t; scanf("%d",&t);

    while (t--){

        solve();

    }

    return 0;

}

Nhận xét

Cảm ơn bạn Đỗ Ngọc Khánh đã giúp tôi hoàn thành bài viết này