2020牛客暑期多校（第一场）I

题目描述

Bobo has a graph with $n$ vertices and m edges where the $i$ -th edge is between the vertices $a_i$ and $b_i$ . Find out whether is possible for him to choose some of the edges such that the $i$ -th vertex is incident with exactly $d_i$ edges.

输入描述

The input consists of several test cases terminated by end-of-file.
The first line of each test case contains two integers $n$ and $m$ .
The second line contains $n$ integers $d_1, d_2, \cdots, d_n$ .
The $i$ -th of the following $m$ lines contains two integers $a_i$ and $b_i$ .
$1 \leqslant n \leqslant 50$ , $1 \leqslant m \leqslant 100$ , $1 \leqslant d_i \leqslant 2$ , $1 \leqslant a_i, b_i \leqslant n$ . $a_i \neq b_i$ , $\{a_i, b_i\} \neq \{a_j, b_j\}$ for $i\neq j$ . The number of tests does not exceed $100$ .

输出描述

For each test case, print Yes without quotes if it is possible. Otherwise, print No without quotes.

示例1

输入

输出

Yes
No
Yes

分析

首先考虑最简单的情况。如果 $\forall\ i\in\mathbb N^\ast$ 且 $1\leqslant i\leqslant n$ ，有 $d_i=1$ ，那么此题可以转化为一般图匹配问题，若最大匹配为完备匹配，则存在满足条件的方案。
进一步考虑当 $d_i=2$ 时的操作。不妨进行拆点，将点 $a$ 拆成点 $a$ 和 $a'$ ，让两者各自找一个点匹配，仍然转化为一般图匹配问题。但是拆点后，由点 $a$ 拆开的两个点可能正好和由点 $b$ 拆开的两点相匹配，为了防止此类情况发生，应当再增加一些限制。
我们可以将一条边 $e$ （ $e$ 的两端分别为点 $a,b$ ）化为两点 $e$ 和 $e'$ ， $e$ 和 $a,a'$ 连边， $e'$ 和 $b,b'$ 连边， $e$ 和 $e'$ 之间连边。若 $e$ 与 $e'$ 之间匹配，那么 $a,a',b,b'$ 四点都不会与之匹配，在原图中的意义为 $a,b$ 之间的边不是一条匹配边；反之，若 $a(a')$ 与 $e$ 匹配， $b(b')$ 与 $e'$ 匹配，在原图上代表 $a,b$ 之间的边是一条匹配边。假如 $a$ 要与 $b$ 匹配， $a'$ 要与 $b'$ 匹配，那么 $e$ 和 $e'$ 就连了不止一条匹配边，这种情况在最大匹配中是不会出现的，因此将边化点的操作是成功的。
建图完成后，若一般图最大匹配为完全匹配，则存在满足条件的方案。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第一场） Problem I
Date: 8/11/2020 
Description: Perfect Matching In General Graph
*******************************************************************/
#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=1003;
struct E
{
    int to;
    int Next=-1;
}edge[N*100];
int n,m;
int father[N];
int head[N],tot;
int color[N],pre[N],match[N],dfn[N];
int timer;
queue<int>q;
int d[N];
int deg[N];
int cnt;
inline void init();
inline void add_edge(int,int);
int father_of(int);
int lca_of(int,int);
void blossom(int,int,int);
bool bfs(int);
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        init();
        int i;
        cnt=n+2*m;
        for(i=1;i<=n;i++) 
        {
            scanf("%d",&d[i]);
            cnt+=d[i]==2;//度为2要拆点
        }
        for(i=1;i<=m;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            if(d[a]==2)
            {
                add_edge(a,n*2+i);//a e
                add_edge(a+n,n*2+i);//a' e
                add_edge(2*n+i,a);//e a
                add_edge(2*n+i,a+n);//e a'
            }
            else 
            {
                add_edge(a,2*n+i);
                add_edge(2*n+i,a);
            }
            if(d[b]==2)
            {
                add_edge(b,n*2+m+i);//b e'
                add_edge(b+n,n*2+m+i);//b' e'
                add_edge(2*n+m+i,b);//e' b
                add_edge(2*n+m+i,b+n);//e' b'
            }
            else 
            {
                add_edge(b,2*n+m+i);
                add_edge(2*n+m+i,b);
            }
            add_edge(2*n+i,2*n+m+i);
            add_edge(2*n+m+i,2*n+i);
        }
        int ans=0;
        for(i=1;i<=2*(n+m);i++)
        {
            if(!match[i])
            {
                ans+=bfs(i);
            }
        }
        puts(ans==cnt>>1?"Yes":"No");
    }
    return 0;
}
inline void init()
{
    tot=0;
    timer=0;
    memset(head,-1,sizeof(head));
    memset(match,0,sizeof(match));
    memset(dfn,0,sizeof(dfn));
}
inline void add_edge(int u,int v)
{
    tot++;
    edge[tot].to=v;
    edge[tot].Next=head[u];
    head[u]=tot;
}
//=============================================
//一般图匹配模板
int father_of(int x)
{
    if(father[x]==x) return x;
    else return father[x]=father_of(father[x]);
}
int lca_of(int x,int y)
{
    timer++;
    x=father_of(x);
    y=father_of(y);
    for(;;x^=y^=x^=y)
    {
        if(x)
        {
            if(dfn[x]==timer) return x;
            dfn[x]=timer;
            x=father_of(pre[match[x]]);
        }
    }
}
void blossom(int x,int y,int lca)
{
    while(father_of(x)!=lca)
    {
        pre[x]=y;
        if(color[match[x]]==1)
        {
            color[match[x]]=0;
            q.push(match[x]);
        }
        if(father[x]==x) father[x]=lca;
        if(father[match[x]]==match[x]) father[match[x]]=lca;
        y=match[x];
        x=pre[y];
    }
}
bool bfs(int x)
{
    int i;
    for(i=1;i<=2*(n+m);i++) father[i]=i;
    memset(color,-1,sizeof(color));
    memset(pre,0,sizeof(pre));
    while(!q.empty()) q.pop();
    color[x]=0;
    q.push(x);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(i=head[u];~i;i=edge[i].Next)
        {
            int v=edge[i].to;
            if(color[v]==-1)
            {
                pre[v]=u;
                color[v]=1;
                if(!match[v])
                {
                    for(register int go=1;go;v=go,u=pre[go])
                    {
                        go=match[u];
                        match[u]=v; 
                        match[v]=u;
                    }
                    return 1;
                }
                color[match[v]]=0;
                q.push(match[v]);
            }
            else if(!color[v]&&father_of(u)!=father_of(v))
            {
                int lca=lca_of(u,v);
                blossom(u,v,lca);
                blossom(v,u,lca);
            }
        }
    }
    return 0;
}

后记

注意初始化。