luogu P4258 [WC2016]挑戰NPC（一般圖的最大匹配，帶花樹，建圖、拆點技巧）

整理的演演算法模板合集： ACM模板

luogu P4258 [WC2016]挑戰NPC

在這裡插入圖片描述

如果是一堆球一堆筐，每一個筐裡只能放一個球，求最大能放多少個球，那麼就是一個二分圖的最大匹配問題，非常簡單，我們一個球一個點作為二分圖的左部，一個筐一個點作為二分圖的右部，直接跑最大流即可。但是這裡我們一個筐不止放一個球，我們一個筐最多可以放三個球，也就是說如果我們一個筐作為一個點的話，我們無法判斷筐內到底放了幾個球，所以我們根據一個筐能放三個球把一個筐拆成三個點，然後我們把一個筐拆成的三個點互相連結。這樣就不再是一個二分圖了，就變成了一個可能有奇環的一般圖，所以很明顯就是一個帶花樹求一般圖匹配問題。

我們根據題意分析所有匹配的情況對答案的貢獻：我們的答案是求最多能有多少個筐，筐裡的球的數量不超過1個。
那麼一共分為三種情況：

非半空的筐子(即裝有 2 或 3 個球)。他們對答案作出的貢獻是無意義的，所以要減去。而他們對答案的影響就是裝有的球數。（如果筐內有三個球，那麼帶花樹求出的答案就是三，但是這三個球實際上對於答案來說沒有任何意義，所以我們要把這求出的3減去）
裝有 1 個球的筐子。他們對答案應作出 1 的貢獻。（如果筐內有一個球，由於筐內三個點有連邊，那麼我們帶花樹求出的答案是2，而我們實際上對答案的貢獻只有1，所以2減去1得1）
空的筐。他們對答案應作出 1 的貢獻。但由於筐的三個點之間有連邊，所以他們對當前答案的貢獻是 1。所以不變。

歸納一下就可以得到，一個筐內裝有多少球，對最終答案造成的應先實際上是帶花樹求出的這個筐內的答案減去球的個數。

由於每個球都必須放入一個筐子, 所以，最終答案就等於帶花樹跑出來的答案減去 n。

拆點的話就參照網路流拆點的方法，把一個點拆成三個點即可。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>

using namespace std;

const int N = 5007, M = 500007, INF = 0x3f3f3f3f;

int n, m;
int dfn[N];
int num, cnt;
int pre[M], match[N];
int head[N], ver[M], nex[M], tot;
int fa[N];
int vis[M], top;
queue<int>q;
int tim;
int t, e;

int ans ;

void add(int x, int y)
{
    ver[tot] = y, nex[tot] = head[x], head[x] = tot ++ ;
    ver[tot] = x, nex[tot] = head[y], head[y] = tot ++ ;
}

int Find(int x)
{
    if(fa[x] == x)return x;
    return fa[x] = Find(fa[x]);
}



//樸素的lca，根據建圖的方式暴力跳
inline int lca(int x, int y)
{
    ++ tim;//時間戳 / 縮點的編號
    while(dfn[x] != tim){
        dfn[x] = tim;//每走一步就標記一下， 如果遇見一個點已經被標記過了就說明這個點已經被另一個點走過了，也就說明是lca
        x = Find(pre[match[x]]);
        if(y)swap(x, y);
    }
    return x;//lca
}
//開花（縮環）
//x和y是要開花的兩個點（此時x和y都是黑點剛找到奇環的時候）
//w是他們的lca
//整個花縮完之後就是一個黑點

//!這裡雖然是兩個點但是隻是從x走到了x和y的lca：w，y到w路徑上的點並沒有染色或者丟到佇列裡去，所以要開兩次，一次x一次y。
inline void blossom(int x, int y, int w)
{
    while(Find(x) != w){
        pre[x] = y;
        y = match[x];
        //如果是白點就直接染成黑色，然後丟到佇列裡面
        vis[y] = 1, q.push(y);
        if(Find(x) == x)fa[x] = w;
        if(Find(y) == y)fa[y] = w;
        x = pre[y];
    }
}

inline bool aug(int s)
{
    for(int i = 1; i <= n + 3 * m; ++ i)
        fa[i] = i, pre[i] = vis[i] = 0;
    while(!q.empty())q.pop();
    q.push(s);
    vis[s] = 1;//從黑點開始
    //佇列中都是黑點，所以遇到相鄰未染色的點都染成白點
    while(!q.empty()){
        int x = q.front();
        q.pop();
        for(int i = head[x] ;~i; i = nex[i]){
            int y = ver[i];
            //如果相鄰點是白點，或者是同一朵花中的節點，則直接跳過這個點
            if(Find(x) == Find(y) || vis[y] == 2) continue;
            if(!vis[y]){//未染色（匹配）點，說明找到了增廣路
                vis[y] = 2;//沒染色就把它染成白色
                pre[y] = x;
                if(!match[y]){
                    int u = y;
                    while(u){
                        int v = pre[u], z = match[v];
                        match[u] = v;match[v] = u;
                        u = z;
                    }
                    return 1;
                }
                vis[match[y]] = 1, q.push(match[y]);
            }
            else {
                int w = lca(x, y);
                blossom(x, y, w);
                blossom(y, x, w);
            }
        }
    }
    return 0;
}

int main()
{
    scanf("%d", &t);
    while(t -- ){
        memset(head, -1, sizeof head);
        memset(dfn, 0, sizeof dfn);
        memset(match, 0 ,sizeof match);
        memset(pre, 0, sizeof pre);
        memset(vis, 0, sizeof vis);
        num = tot = tim = cnt = 0;
        scanf("%d%d%d", &n, &m, &e);
        for(int i = 1; i <= e; ++ i){
            int x, y;
            scanf("%d%d", &x, &y);
            //拆成三個點
            add(x, y + n);
            add(x, y + n + m);
            add(x, y + n + 2 * m);
        }
        for(int i = 1; i <= m; ++ i){
            add(i + n, i + n + m);
            add(i + n, i + n + m * 2);
            add(i + n + m, i + n + m * 2);
        }
        ans = 0;
        for(int i = 1; i <= n + m * 3 ; ++ i){
            if(!match[i])
                ans += aug(i);
        }
        printf("%d\n", ans - n);

        for(int i = 1; i <= n; ++ i)
            printf("%d ", (match[i] - n - 1) % m + 1);
    }
    return 0;
}