I 一般图最大匹配

思路

一看就是个匹配问题，不过属于多重匹配。我们可以通过拆点，拆成一般匹配。留意到 $d[i]$ 很小，可以直接把点 $i$ 拆成 $d[i]$ 个点，这些点记为 $p[i]$

为了保留匹配关系，还需要拆边。对于边$(u, v)$：

  1. 先建立两个中介点$x, y$
  2. 将 $p[u]$ 所有点和 $x$ 连接 (无向边)
  3. 将 $p[v]$ 所有点和 $y$ 连接 (无向边)
  4. 连接中介点 $x, y$ (无向边)

例子：

d = [1, 1, 2]
e = [(1, 3), (2, 3)]

首先拆点：

p[1] = [1]
p[2] = [2]
p[3] = [3, 4]

然后拆边，并连边:

  1. (1, 3): 中介点(5, 6), 连接(1, 5), (3, 6), (4, 6), (5, 6)
  2. (2, 3): 中介点(7, 8), 连接(2, 7), (3, 8), (4, 8), (7, 8)

然后在上图跑一般图最大匹配，如果有解，一定所有的点都匹配上。(可画图证明)

代码

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int N = 1e3 + 5;
const int M = 1e4 + 5;
const int inf = 1LL << 30;

struct edge
{
    int v, nxt;
};

edge e[M << 1];
int head[N], tot;

int match[N], pre[N], type[N];
int que[N], qhead, qtail;
int ft[N];

inline void init()
{
    memset(match, 0, sizeof(match));
    memset(head, -1, sizeof(head));
    tot = 0;
}

inline void addEdge(int u, int v)
{
    e[tot] = edge{v, head[u]};
    head[u] = tot++;
}

inline int find(int x)
{
    return ft[x] == x ? x : ft[x] = find(ft[x]);
}

inline int getLca(int u, int v)
{
    static int ss[N], tim;
    tim++;
    while (ss[u] != tim)
    {
        if (u)
        {
            ss[u] = tim;
            u = find(pre[match[u]]);
        }
        swap(u, v);
    }
    return u;
}

inline void flower(int x, int y, int p)
{
    while (find(x) != p)
    {
        pre[x] = y;
        y = match[x];
        ft[x] = ft[y] = p;
        if (type[y] == 1)
        {
            que[qtail++] = y;
            type[y] = 2;
        }
        x = pre[y];
    }
}

inline bool blossom(int u, int n)
{
    qhead = qtail = 0;
    for (int i = 1; i <= n; i++)
    {
        type[i] = 0;
        ft[i] = i;
    }
    que[qtail++] = u;
    type[u] = 2;
    while (qhead != qtail)
    {
        u = que[qhead++];
        for (int i = head[u]; ~i; i = e[i].nxt)
        {
            int v = e[i].v;
            if (type[v] == 0)
            {
                type[v] = 1;
                pre[v] = u;
                if (!match[v])
                {
                    while (u)
                    {
                        u = match[pre[v]];
                        match[v] = pre[v];
                        match[match[v]] = v;
                        v = u;
                    }
                    return true;
                }
                else
                {
                    que[qtail++] = match[v];
                    type[match[v]] = 2;
                }
            }
            else if (type[v] == 2 && find(u) != find(v))
            {
                int p = getLca(u, v);
                flower(u, v, p);
                flower(v, u, p);
            }
        }
    }
    return false;
}

int d[N], id[N], od[N];
vector<int> p[N];

int main()
{
    int n, m;
    while (~scanf("%d%d", &n, &m))
    {
        init();
        int tot = 0, ans = 0;
        memset(id, 0, sizeof(id));
        memset(od, 0, sizeof(od));
        for (int i = 1; i <= n; i++)
        {
            p[i].clear();
            scanf("%d", &d[i]);
            for (int j = 0; j < d[i]; ++j) {
                id[++tot] = i;
                p[i].push_back(tot);
            }
        }

        while (m--)
        {
            int u, v;
            scanf("%d%d", &u, &v);
            int x = ++tot, y = ++tot;
            for (auto u0 : p[u])
                addEdge(u0, x), addEdge(x, u0);
            for (auto v0 : p[v])
                addEdge(v0, y), addEdge(y, v0);
            addEdge(x, y), addEdge(y, x);
            od[u]++, od[v]++;
        }

        bool err = 0;
        for (int i = 1; i <= n; i++) {
            if (od[i] < d[i]) {
                puts("No");
                err = 1;
                break;
            }
        }
        if (err) continue;
        for (int i = 1; i <= tot; i++)
            if (!match[i] && blossom(i, tot))
                ans++;

        int count = 0;
        for (int i = 1; i <= tot; i++) 
            count += !!(match[i]);

        if (count == tot) 
            puts("Yes");
        else 
            puts("No");
    }
    return 0;
}