一般图最大匹配 带花树 2020牛客暑期多校训练营（第二场）I 1 or 2

一般图最大匹配 带花树 2020牛客暑期多校训练营（第一场）I 1 or 2

标签（空格分隔）： 一般图最大匹配

---

kuangbin的模板https://www.cnblogs.com/kuangbin/p/3278621.html
求一般图最大匹配，这道题的难点在于建图，把每个节点分成它的度个节点，把每条边分成两个节点，之后对于每条边，两个边分成的节点相连，边的两个端点的节点分别与其端点分成的度个节点相连之后求最大匹配，如果为完美匹配，则为Yes，否则No。对于完美匹配，若一个边的一个端点不与由点分解的节点相连，那对映的另一个段点必与他匹配，否则就不是完美匹配了；若该边的的一个点与点分解的节点相连，则意味着这条边被选择，其另一端也必与点分解的节点相连；对于完美匹配，每个点分解的点都被连向边分解的点。这样一个符合条件的解就对应一个完美匹配。
参考https://www.cnblogs.com/xiongtao/p/11189452.html

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1e3+10;
int n,m;
int N;
bool Graph[MAXN][MAXN];
int Match[MAXN];
bool InQueue[MAXN],InPath[MAXN],InBlossom[MAXN];
int Head,Tail;
int Queue[MAXN];
int Start,Finish;
int NewBase;
int Father[MAXN],Base[MAXN];
int Count;//匹配数，匹配对数是Count/2

void Push(int u)
{
    Queue[Tail] = u;
    Tail++;
    InQueue[u] = true;
}
int Pop()
{
    int res = Queue[Head];
    Head++;
    return res;
}
int FindCommonAncestor(int u,int v)
{
    memset(InPath,false,sizeof(InPath));
    while(true)
    {
        u = Base[u];
        InPath[u] = true;
        if(u == Start) break;
        u = Father[Match[u]];
    }
    while(true)
    {
        v = Base[v];
        if(InPath[v])break;
        v = Father[Match[v]];
    }
    return v;
}
void ResetTrace(int u)
{
    int v;
    while(Base[u] != NewBase)
    {
        v = Match[u];
        InBlossom[Base[u]] = InBlossom[Base[v]] = true;
        u = Father[v];
        if(Base[u] != NewBase) Father[u] = v;
    }
}
void BloosomContract(int u,int v)
{
    NewBase = FindCommonAncestor(u,v);
    memset(InBlossom,false,sizeof(InBlossom));
    ResetTrace(u);
    ResetTrace(v);
    if(Base[u] != NewBase) Father[u] = v;
    if(Base[v] != NewBase) Father[v] = u;
    for(int tu = 1; tu <= N; tu++)
        if(InBlossom[Base[tu]])
        {
            Base[tu] = NewBase;
            if(!InQueue[tu]) Push(tu);
        }
}
void FindAugmentingPath()
{
    memset(InQueue,false,sizeof(InQueue));
    memset(Father,0,sizeof(Father));
    for(int i = 1;i <= N;i++)
        Base[i] = i;
    Head = Tail = 1;
    Push(Start);
    Finish = 0;
    while(Head < Tail)
    {
        int u = Pop();
        for(int v = 1; v <= N; v++)
            if(Graph[u][v] && (Base[u] != Base[v]) && (Match[u] != v))
            {
                if((v == Start) || ((Match[v] > 0) && Father[Match[v]] > 0))
                    BloosomContract(u,v);
                else if(Father[v] == 0)
                {
                    Father[v] = u;
                    if(Match[v] > 0)
                        Push(Match[v]);
                    else
                    {
                        Finish = v;
                        return;
                    }
                }
            }
    }
}
void AugmentPath()
{
    int u,v,w;
    u = Finish;
    while(u > 0)
    {
        v = Father[u];
        w = Match[v];
        Match[v] = u;
        Match[u] = v;
        u = w;
    }
}
void Edmonds()
{
    memset(Match,0,sizeof(Match));
    for(int u = 1; u <= N; u++)
        if(Match[u] == 0)
        {
            Start = u;
            FindAugmentingPath();
            if(Finish > 0)AugmentPath();
        }
}
void PrintMatch()
{
    Count = 0;
    for(int u = 1; u <= N;u++)
        if(Match[u] > 0)
            Count++;
    printf("%d\n",Count);
    for(int u = 1; u <= N; u++)
        if(u < Match[u])
            printf("%d %d\n",u,Match[u]);
}



int main()
{
    while(~scanf("%d%d",&n,&m)){
        vector<int>vec[MAXN];
        memset(Graph,false,sizeof(Graph));
        memset(Match,0,sizeof(Match));
        memset(InQueue,0,sizeof(InQueue));
        memset(InPath,0,sizeof(InPath));
        memset(InBlossom,0,sizeof(InBlossom));
        memset(Base,0,sizeof(Base));
        memset(Queue,0,sizeof(Queue));
        memset(Father,0,sizeof(Father));
        Head=Tail=Start=Finish=Count=NewBase=0;
        N=0;
        for(int i=1;i<=n;i++){
            int d;
            scanf("%d",&d);
            while(d--){
                vec[i].push_back(++N);
            }
        }
        for(int i=1;i<=m;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            int f=++N;
            int t=++N;
            Graph[f][t]=Graph[t][f]=true;
            for(int i=0;i<vec[u].size();i++)
                Graph[vec[u][i]][f]=Graph[f][vec[u][i]]=true;
            for(int i=0;i<vec[v].size();i++)
                Graph[vec[v][i]][t]=Graph[t][vec[v][i]]=true;
        }
        Edmonds();
        int cnt=0;
        for(int i=1;i<=N;i++){
            if(Match[i]>0)
                cnt++;
        }
        if(cnt==N)
            puts("Yes");
        else
            puts("No");
    }
}

本文地址：https://blog.csdn.net/qq_44290978/article/details/107326904