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

luogu P4258 [WC2016]挑战NPC

如果是一堆球一堆筐，每一个筐里只能放一个球，求最大能放多少个球， 那么就是一个二分图的最大匹配问题，非常简单，我们一个球一个点作为二分图的左部，一个筐一个点作为二分图的右部，直接跑最大流即可。但是这里我们一个筐不止放一个球，我们一个筐最多可以放三个球，也就是说如果我们一个筐作为一个点的话，我们无法判断筐内到底放了几个球，所以我们根据一个筐能放三个球把一个筐拆成三个点，然后我们把一个筐拆成的三个点互相链接。这样就不再是一个二分图了，就变成了一个可能有奇环的一般图，所以很明显就是一个带花树求一般图匹配问题。

我们根据题意分析所有匹配的情况对答案的贡献：我们的答案是求最多能有多少个筐，筐里的球的数量不超过1个。
那么一共分为三种情况：

1. 非半空的筐子(即装有 2 或 3 个球)。他们对答案作出的贡献是无意义的，所以要减去。而他们对答案的影响就是装有的球数。（如果筐内有三个球，那么带花树求出的答案就是三，但是这三个球实际上对于答案来说没有任何意义，所以我们要把这求出的3减去）
2. 装有 1 个球的筐子。他们对答案应作出 1 的贡献。（如果筐内有一个球，由于筐内三个点有连边，那么我们带花树求出的答案是2，而我们实际上对答案的贡献只有1，所以2减去1得1）
3. 空的筐。他们对答案应作出 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;
}