转送门

题意是说给n个点m条边，能否选出一些边使得每个点恰好又d[i]个度。d[i]只有1或者2。

做法是每条边拆成x, y两个点，互连。边的两个点i拆成d[i]个点与x连，j拆成d[j]个点与y连。

然后做一般图匹配，判断是否有完美匹配。

可以被证明，当x取模S域的随机数时，错误概率不会高于n/S

于是建起这个矩阵高斯消元即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
mt19937 mrand(random_device{}()); // mrand是给定随机数种子的的大随机数对象
int rnd(int x) { return mrand() % x;}
const double eps = 1e-6;
const int maxn = 433;
ll a[maxn][maxn];
ll mod = 1e9 + 7;
ll ksm(ll n, ll k)
{
    ll res = 1;
    while(k)
    {
        if(k & 1) res = res * n % mod;
        n = n * n % mod;
        k >>= 1;
    }
    return res;
}
int gauss(int n)
{
    int c, r;
    for (c = 0, r = 0; c < n; c ++ )
    {
        int t = r;
        for (int i = r; i < n; i ++ )
            if (a[i][c] != 0)
                t = i;

        if (a[t][c] == 0) continue;

        for (int i = c; i < n; i ++ ) swap(a[t][i], a[r][i]);
        //a[r][c] %= mod;
        ll inv = ksm(a[r][c], mod - 2);
        for (int i = n; i >= c; i -- ) a[r][i] = a[r][i] * inv % mod;

        for (int i = r + 1; i < n; i ++ )
                for (int j = n; j >= c; j -- )
                    a[i][j] = (a[i][j] - a[r][j] * a[i][c] % mod) % mod;

        r ++ ;
    }
    // for(int i = 0; i < n; i++)
    //     for(int j = 0; j < n; j++) printf("%d%c", a[i][j]," \n"[j == n - 1]);

    ll res = 1;
    for(int i = 0; i < n; i++) res = res * a[i][i] % mod;
    return res % mod;
}
int d[55], s[maxn];
int mp[55][55];
int main()
{
    int n, m; 
    while(~scanf("%d%d", &n, &m))
    {
        memset(mp, 0, sizeof mp);
        memset(a, 0, sizeof a);
        for(int i = 0; i < n; i++) scanf("%d", &d[i]);
        for(int i = 0; i < n; i++) s[i + 1] = s[i] + d[i];
        for(int i = 0; i < m; i++) 
        {
            int u, v; scanf("%d%d", &u, &v);
            u--, v--;
            mp[u][v] ++; mp[v][u]++;
        }

        for(int i = 0; i < n; i++)
            for(int j = i + 1; j < n; j++)
            {
                if(mp[i][j] == 0) continue;
                for(int k = 0; k < min(2, mp[i][j]); k++)
                {
                    ll rd = 0;
                    for(int l = 0; l < d[i]; l++)
                    {
                        rd = rnd(mod);
                        a[s[i] + l][s[n]] = rd;
                        a[s[n]][s[i] + l] = -rd; 
                    }
                    rd = rnd(mod);
                    a[s[n]][s[n] + 1] = rd;
                    a[s[n] + 1][s[n]] = -rd;
                    s[n] ++;
                    for(int r = 0; r < d[j]; r++)
                    {
                        rd = rnd(mod);
                        a[s[j] + r][s[n]] = rd;
                        a[s[n]][s[j] + r] = -rd;
                    }
                    s[n]++;
                }
            }
        // cerr << "\n------\n";
        // for(int i = 0; i < s[n]; i++)
        // for(int j = 0; j < s[n]; j++) printf("%d%c", a[i][j]," \n"[j == s[n] - 1]);
        // cerr << "\n------\n";
        if(gauss(s[n]) != 0) printf("Yes\n");
        else printf("No\n");

    }


}