模板汇总 ——— 匈牙利算法-白红宇

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

阅读量：5813 次

发布时间：2019-06-18

本文共 2506 字，大约阅读时间需要 8 分钟。

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

模板

#include
      
       #include
       
        #include
        
         #include
         
          #include
          #include
           
            #include
            
             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
             
               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;}