题目链接

题面：

题意：
给定一张图，然后给定一些点的度数，问能不能通过删边来使得图中每个点的度数与给定的度数相等。

题解：
考虑一般图的最大匹配。
如果点 i 给定的度数是 di，那么我们把 i 拆分为di个点。
这样如果这di个点都在最大匹配当中，那么说明 i 点的度数符合要求。
如果原图中 i 与 j 有边相连，那么 di 个 i 点与 dj 个 j 点分别相连。

通过观察发现，如果di，dj不全大于等于2，那么这样连边是符合要求的。
假设 di = 1，dj = 2
那么 i – j，i – jj ，这样只能贡献一个匹配。

若di = 2，dj = 2
那么 i – j，i – jj，ii – j，ii – jj，这样就会出现一条边对于一个点贡献两个度的情况。
我们考虑把这条边拆开。
i – e，ii – e，j – ee，jj – ee，e – ee
然后再求一般图最大匹配。

若最终是 e 与 ee 匹配，那么说明我们不需要这条边，否则我们需要 e 与 i 的某个拆点匹配，ee 与 j 的某个拆点匹配，说明这条边需要。
那么最终，每个点都需要有与之匹配的点才可行。

假设拆点后的点的个数为cnt，那么我们求出的最大匹配ans*2==cnt才成立。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
//#define lc (cnt<<1)
//#define rc (cnt<<1|1)
#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
using namespace std;

const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=998244353;
const double eps=1e-8;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=510;
const int maxm=100100;
const int up=1000;

int head[maxn],ver[maxn*maxn],nt[maxn*maxn],tot;
int ha[maxn],match[maxn],pre[maxn],f[maxn],id[maxn];
int n,m,idx,cnt,d[maxn],xx[maxn],yy[maxn];
bool use[maxn];
queue<int>q;

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

void div(int x)
{
    if(use[x]) return;
    xx[x]=++cnt;
    if(d[x]==2) yy[x]=++cnt;
}

int fi(int x)
{
    if(f[x]!=x)
        f[x]=fi(f[x]);
    return f[x];
}

void init(void)
{
    idx=tot=cnt=0;
    memset(head,0,sizeof(head));
    memset(id,0,sizeof(id));
    memset(match,0,sizeof(match));
    memset(use,0,sizeof(use));
}

int LCA(int x,int y)
{
    for(idx++,x=fi(x),y=fi(y);;swap(x,y))
    {
        if(x)
        {
            if(id[x]==idx) return x;
            id[x]=idx,x=fi(pre[match[x]]);
        }
    }
}

void blossom(int x,int y,int lca)
{
    while(fi(x)!=lca)
    {
        pre[x]=y;y=match[x];
        if(ha[y]==2) ha[y]=1,q.push(y);
        if(fi(x)==x) f[x]=lca;
        if(fi(y)==y) f[y]=lca;
        x=pre[y];
    }
}

int bfs(int s)
{
    for(int i=1;i<=n;i++)
        ha[i]=pre[i]=0,f[i]=i;
    while(q.size()) q.pop();
    q.push(s);
    ha[s]=1;

    while(q.size())
    {
        int x=q.front();
        q.pop();

        for(int i=head[x];i;i=nt[i])
        {
            int y=ver[i];
            if(fi(x)==fi(y)||ha[y]==2) continue;
            if(!ha[y])
            {
                ha[y]=2;pre[y]=x;
                if(!match[y])
                {
                    for(int k=y,last;k;k=last)
                        last=match[pre[k]],match[k]=pre[k],match[pre[k]]=k;
                    return 1;
                }
                ha[match[y]]=1,q.push(match[y]);
            }
            else
            {
                int lca=LCA(x,y);
                blossom(x,y,lca),blossom(y,x,lca);
            }
        }
    }
    return 0;
}

int main(void)
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init();
        for(int i=1;i<=n;i++)
            scanf("%d",&d[i]),div(i);
        int x,y;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&x,&y);;
            if(d[x]==1&&d[y]==1)
            {
                add(xx[x],xx[y]);
            }
            else if(d[x]==1&&d[y]==2)
            {
                add(xx[x],xx[y]);
                add(xx[x],yy[y]);
            }
            else if(d[x]==2&&d[y]==1)
            {
                add(xx[x],xx[y]);
                add(yy[x],xx[y]);
            }
            else
            {
                int e1=++cnt,e2=++cnt;
                add(xx[x],e1);
                add(yy[x],e1);
                add(e1,e2);
                add(xx[y],e2);
                add(yy[y],e2);
            }
        }
        n=cnt;
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            if(!match[i])
                ans+=bfs(i);
        }
        if(ans*2==cnt) printf("Yes\n");
        else printf("No\n");
    }

    return 0;
}