2020牛客暑期多校训练营（第一场）补题记录

I

题意

题目给出了一个图，然后还有n个点，还有每个点的度，求判断图中是否存在一个子图满足每个点的度等于给出的度，度为[1,2]。

思路

首先，如果每个点的度都为1，那么很显然，直接求这个图是否存在完全匹配就可以了。但是度数的范围是[1,2]，于是我们就想到拆点，如果是简单的把度为2的点直接拆成两个点的话，就会有下面这种情况

当我要求d[1]=d[2]=2的时候

注：图中的边全都为无向边

直接拆点会变成

显然存在完美匹配，但是根据原图来看是不可能存在这种情况的。所以我们改进拆点，分析一下上面的建图为什么会错，是因为我们没有保证一条边只提供一个度，而是可以提供多个度，所以要修改成这样

改成这样，就可以保证一条边只提供一个度了，很显然上面的图不存在完美匹配，再画一个简单的1-2-3的构图

建好这个图之后只需要判断是否存在完美匹配就好了，跑一遍带花树的板子即可。

代码实现

#include<bits/stdc++.h>
using namespace std;
// graph
const int maxn = 200;
struct blossemtree{
    int n;
    vector<int>g[maxn];
    queue<int>q;
    int fa[maxn];
    int type[maxn],link[maxn],Next[maxn],vis[maxn];
    int find(int x){
        if(x==fa[x]) return x;
        return fa[x]=find(fa[x]);
    }
    void add(int u,int v){
        g[u].push_back(v);
        g[v].push_back(u);
    }
    void combine(int x,int lca){
        while(x!=lca){
            int u=link[x],v=Next[u];
            if(find(v)!=lca) Next[v]=u;
            if(type[u]==1) type[u]=2,q.push(u);
            fa[find(x)]=find(u);
            fa[find(u)]=find(v);//注意这里不能直接写成lca
            x=v;
        }
    }
    void contrack(int x,int y){
        int lca=x;
        memset(vis,0,sizeof(vis));
        for(int i=x;i;i=Next[link[i]]){
            i=find(i);
            vis[i]=1;
        }
        for(int i=y;i;i=Next[link[i]]){
            i=find(i);
            if(vis[i]){
                lca=i;
                break;
            }
        }
        if(lca!=find(x)) Next[x]=y;if(lca!=find(y)) Next[y]=x;
        combine(x,lca);
        combine(y,lca);
    }
    void bfs(int S){
        memset(type,0,sizeof(type));
        memset(Next,0,sizeof(Next));
        for(int i=1;i<=n;i++) fa[i]=i;
        while(!q.empty()) q.pop();
        q.push(S);type[S]=2; //这里之前写成 type[S]=1了，抱歉！
        while(!q.empty()){
            int x=q.front();
            q.pop();
            for(int i=0;i<g[x].size();i++){
                int y=g[x][i];
                if(find(x)==find(y) || link[x]==y || type[y]==1) continue;
                if(type[y]==2) contrack(x,y);
                else if(link[y]){
                    Next[y]=x;
                    type[y]=1;
                    type[link[y]]=2;
                    q.push(link[y]);
                }
                else{
                    Next[y]=x;
                    int pos=y,u=Next[pos],v=link[u];
                    while(pos){
                        link[pos]=u;link[u]=pos;
                        pos=v;
                        u=Next[pos];v=link[u];
                    }
                    return;
                }
            }
        }
    }
    int maxmatch(){
        for(int i=1;i<=n;i++)
            if(!link[i])
                bfs(i);
        int ans=0;
        for(int i=1;i<=n;i++) if(link[i]) ans++;
        return ans;//返回能够匹配的边数
    }
    void init(int n){
        this->n = n;
        for(int i=1;i<=n;i++) g[i].clear();
        memset(link,0,sizeof(link));
    }
}tree;
vector<pair<int,int>>edges;
int id[55][3];
int d[55];
int idd[55];
int build(int n){
    int  num = 0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=d[i];j++){
            id[i][j]=++num;
        }
    }
    for(int i=1;i<=n;i++){
        idd[i]=++num;
    }
    tree.init(maxn-1);
    for(int i=0;i<edges.size();i++){
        int u = edges[i].first;
        int v = edges[i].second;
        for(int j=1;j<=d[u];j++){
            tree.add(id[u][j],num+1);
            //printf("%d %d\n",id[u][j],num+1);
        }
        for(int j=1;j<=d[v];j++){
            tree.add(id[v][j],num+2);
            //printf("%d %d\n",id[v][j],num+2);
        }
        tree.add(num+1,num+2);
        //printf("%d %d\n",num+1,num+2);
        num+=2;
    }
    return num;
}
void Scanner(int n,int m){
    int sum = 0;
    for(int i=1;i<=n;i++)scanf("%d",&d[i]),sum+=d[i];
    edges.clear();
    for(int i=0;i<m;i++){
        int u,v;
        scanf("%d %d",&u,&v);
        edges.push_back(make_pair(u,v));
    }
    int num = build(n);
    int ans = tree.maxmatch();
    if(ans==num)printf("Yes\n");
    else printf("No\n");
}
int main(){
    int n,m;
    while(scanf("%d %d",&n,&m)!=EOF)Scanner(n,m);
    return 0;
}