模板汇总 ——— 匈牙利算法

佚名 6年前 (2019-04-14) 随笔 1256人围观抢沙发百度已收录

const int N = 500;
const int M = 1e5;
int head[N], to[M], nt[M], link[M], tot;
int vis[N];
int Vcnt;
int n, m;
void add(int u, int v){
    to[tot] = v;
    nt[tot] = head[u];
    head[u] = tot++;

    to[tot] = u;
    nt[tot] = head[v];
    head[v] = tot++;
}
bool hun(int u){
    for(int i = head[u]; ~i; i = nt[i]){
        if(vis[to[i]] != Vcnt){
            vis[to[i]] = Vcnt;
            if(-1 == link[to[i]] ||  hun(link[to[i]])){
                link[u] = to[i];
                link[to[i]]=u;
                return 1;
            }
        }
    }
    return 0;
}
int solve(int n){
    for(int i = 1; i <= n; ++i){
        if(link[i] == -1){
            ++Vcnt;
            if(!hun(i))
                return false;
        }
    }
    return true;
}
void init(){
    memset(head, -1, sizeof head);
    memset(link, -1, sizeof link);
    memset(vis, 0, sizeof vis);
    Vcnt = 0;
    tot = 0;
}

View Code

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<iostream>
#include<cstring>
using namespace std;
#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
#define LL long long
#define ULL unsigned LL
#define fi first
#define se second
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define lch(x) tr[x].son[0]
#define rch(x) tr[x].son[1]
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
typedef pair<int,int> pll;
const int inf = 0x3f3f3f3f;
const int _inf = 0xc0c0c0c0;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL _INF = 0xc0c0c0c0c0c0c0c0;
const LL mod =  (int)1e9+7;
const int N = 500;
const int M = 1e5;
int head[N], to[M], nt[M], link[M], tot;
int vis[N];
int Vcnt;
int n, m;
void add(int u, int v){
    to[tot] = v;
    nt[tot] = head[u];
    head[u] = tot++;
}
bool hun(int u){
    for(int i = head[u]; ~i; i = nt[i]){
        if(vis[to[i]] != Vcnt){
            vis[to[i]] = Vcnt;
            if(-1 == link[to[i]] ||  hun(link[to[i]])){
                link[u] = to[i];
                link[to[i]]=u;
                return 1;
            }
        }
    }
    return 0;
}
int solve(int n){
    for(int i = 1; i <= n; ++i){
        if(link[i] == -1){
            ++Vcnt;
            if(!hun(i))
                return false;
        }
    }
    return true;
}
void init(){
    memset(head, -1, sizeof head);
    memset(link, -1, sizeof link);
    memset(vis, 0, sizeof vis);
    Vcnt = 0;
    tot = 0;
}
int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        scanf("%d%d", &n, &m);
        init();
        for(int i = 1; i <= n; ++i){
            int t, v;
            scanf("%d", &t);
            while(t--){
                scanf("%d", &v);
                add(i, v+n);
                add(v+n, i);
            }
        }
        if(solve(n)) puts("YES");
        else puts("NO");
    }
    return 0;
}