1 条题解

  • 0
    @ 2026-5-7 20:49:04

    本题解为矩阵树定理博客节选内容，完整版详见此处。

    1. BEST 定理

    定理 11（有向欧拉回路的判定法则）：若有向图 GG 强连通，且对于 GG 中的每个点均有 $\mathrm{deg}^{\mathrm{in}} = \mathrm{deg}^{\mathrm{out}}$。

    根据这个定理，我们可以延伸出 BEST 定理的作用：求有向图中欧拉回路的个数。

    需要注意的是，普通无向图中欧拉回路的计数是 NPC，无法在多项式时间复杂度内解决。

    定理 22（BEST 定理）：若有向图中存在欧拉回路，那么它的欧拉回路个数为 $\mathrm{ec}(G) = t^{\mathrm{root}}(G, k)\times \prod_{i=1}^n (\deg(i) - 1)!$。其中 kk 为 1∼n1\sim n 中的任意一个正整数。

    其中，deg⁡(v)\deg(v) 表示点 vv 的出度 / 入度。因为当有向图存在欧拉回路的时候，必然有 deg⁡in=deg⁡out\deg^{\mathrm{in}} = \deg^{\mathrm{out}}。同理，troot(G,k)t^{\mathrm{root}}(G, k) 和 tleaf(G,k)t^{\mathrm{leaf}}(G, k) 在标准的 BEST 定理上也是等价的。

    证明：
    将定理的形式转化为 $\deg(k)\times \mathrm{ec}(G) = t^{\mathrm{root}}(G, k)\times \deg(k)!\times \prod_{1\le i \le n, i\ne k} (\deg(i) - 1)!$。
    等式右侧的意义为：从欧拉回路中选出每个点（点 kk 除外）最后走的那条边，这些边一定构成了一个以 kk 为根的根向树形图。然后点 kk 和其他点都随便钦定出边的顺序，按照每个点出边的顺序走就一定能构成欧拉回路。
    等式左侧还有个 deg⁡(k)\deg(k) 的原因是，循环同构的欧拉回路算作同一个欧拉回路，需要用除法去掉。例如 1→2→1→3→11\to 2\to 1\to 3\to 1 和 1→3→1→2→11\to 3\to 1\to 2\to 1 是同一个欧拉回路。
    接下来证明除 kk 以外，其余点最后走的那条边一定构成根向树形图。
    因为一共只有 n−1n-1 条边，所以我们只需要证明子图中不存在环即可。
    考虑反证法，如果子图中存在环，那么想要构成欧拉回路，环上必然存在一条边，排在所谓的“最后一条边”后面，并且直接或者间接地指向 kk。那么就说明了这些边并不是最后走的一条边，与题设矛盾，因此子图中不存在环。
    注意这只是一个不严谨的证明，想要看严谨证明的可以参考 OIwiki 中的双射构造。

    需要注意的是，如果我们不把循环同构的回路当做同一个欧拉回路，那么等式左侧就不要加那个 deg⁡(k)\deg(k)，那么公式就变为了 $\mathrm{ec}(G) = t^{\mathrm{root}}(G, k)\times \deg(k)!\times \prod_{1\le i \le n, i\ne k} (\deg(i) - 1)!$。

    2.1 P5807 【模板】BEST 定理 / Which Dreamed It

    这就是上文中“循环同构不算同一个欧拉回路”的例子。直接套用 BEST 定理的公式计算即可。注意需要判断图中是否存在欧拉回路，并且有的点可能是孤立点。

    时间复杂度 O(n3)O(n^3)。

    #include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef __int128 i128;
using pi = pair<int, int>;
const int N = 105, V = 1e6 + 5;
const ll mod = 1e6 + 3;
ll n, a[N][N], b[N][N], degin[N], degout[N], inv[V], f[V];
int low[N], dfn[N], tot, cnt, scc[N], stk[N], tp;
bitset<N> instk;
vector<int> g[N];
void init()
{
    inv[1] = 1; f[0] = f[1] = 1;
    for(int i = 2; i < mod; i++)
    {
        f[i] = (f[i - 1] * i) % mod;
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    }
}
void tarjan(int u)
{
    low[u] = dfn[u] = ++tot;
    stk[++tp] = u; instk[u] = 1;
    for(auto v : g[u])
    {
        if(!dfn[v])
        {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if(instk[v])
        {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if(low[u] == dfn[u])
    {
        int x;
        ++cnt;
        do{
            x = stk[tp--];
            scc[x] = cnt;
            instk[x] = 0;
        } while(u != x);
    }
}
bool check()
{
    for(int i = 1; i <= n; i++)
        if(degin[i] ^ degout[i])
            return 0;
    for(int i = 1; i <= n; i++)
        if(!dfn[i])
            tarjan(i);   
    for(int i = 1; i <= n; i++)
    {
        if(degout[i] == 0) continue;
        if(scc[1] != scc[i]) return 0;
    } 
    return 1;
}
ll Det(ll n, ll a[N][N])
{
    bool flag = 0; ll res = 1;
    auto Swap = [&] (int x, int y) -> void {
        swap(a[x], a[y]); flag ^= 1;
    };
    for(int i = 1; i <= n; i++)
    {
        for(int j = i; j <= n; j++)
        {
            if(a[j][i])
            {
                if(i ^ j) Swap(i, j);
                break;
            }
        }
        if(!a[i][i]) return 0;
        a[i][i] = (a[i][i] % mod + mod) % mod;
        for(int j = i + 1; j <= n; j++)
        {
            ll c = a[j][i] * inv[a[i][i]] % mod;
            for(int k = i; k <= n; k++)
                a[j][k] = (a[j][k] - c * a[i][k]) % mod;
        }
        res = (res * a[i][i]) % mod;
    }
    if(flag) res = -res;
    return (res % mod + mod) % mod;
}
void solve()
{
    memset(a, 0, sizeof(a));
    memset(degin, 0, sizeof(degin));
    memset(degout, 0, sizeof(degout));
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
    memset(scc, 0, sizeof(scc));
    instk.reset();
    tp = tot = cnt = 0;
    cin >> n;
    for(int i = 1; i <= n; i++) g[i].clear();
    int smx = 0;
    for(int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        smx += x;
        a[i][i] += x;
        degout[i] = x;
        if(x == 0) a[i][i] = 1, a[i][1] = -1;
        while(x--)
        {
            int v;
            cin >> v;
            a[i][v]--;
            degin[v]++;
            g[i].push_back(v);
        }
    }
    if(!check())
    {
        cout << "0\n";
        return;
    }
    if(smx == 0)
    {
        cout << "1\n";
        return;
    }
    for(int i = 1; i < n; i++)
        for(int j = 1; j < n; j++)
            b[i][j] = a[i + 1][j + 1];
    ll res = Det(n - 1, b);
    res = (res * f[degout[1]]) % mod;
    for(int i = 2; i <= n; i++)
    {
        if(degout[i] == degin[i] && degout[i] == 0) continue;
        res = (res * f[degout[i] - 1]) % mod;
    }
    cout << res << "\n";
}
int main()
{
    //freopen("sample.in", "r", stdin);
    //freopen("sample.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    init();
    int t;
    cin >> t;
    while(t--) solve();
    return 0;
}

    2.2 P7531 [USACO21OPEN] Routing Schemes P

    这有黑？这有黑？这有黑？这有黑？这有黑？

    容易想到网络流里建立超级源点、超级汇点的思路，然后把超级汇点朝超级源点连一条边，那么问题就被转化为对有向图的欧拉回路计数，套用 BEST 定理即可解决。时间复杂度 O(Tn3)O(Tn^3)。

    注意因为欧拉回路中各路径的顺序并不会影响最后答案的计数，所以答案要除以 S!×(S−1)!S!\times (S-1)!。其中 SS 表示起点的个数。这个式子的含义是，除以 S!S! 代表去掉“从超级汇点走向超级源点选择不同边”的方案；而除以 (S−1)!(S-1)! 代表去掉从超级源点出发选择的不同路径的顺序，不是除以 S!S! 的原因是 BEST 定理已经去掉了循环同构的欧拉回路。

    #include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef __int128 i128;
using pi = pair<int, int>;
const int N = 105;
const ll mod = 1e9 + 7;
int n, m, s, t;
ll a[N][N], b[N][N], f[N];
bitset<N> legal;
void init()
{
    f[0] = 1;
    for(int i = 1; i < N; i++)
        f[i] = (f[i - 1] * i) % mod;
}
void add(int u, int v, int w)
{
    a[u][u] += w;
    a[u][v] -= w;
}
ll qpow(ll a, ll b)
{
    ll res = 1;
    while(b)
    {
        if(b & 1) res = (res * a) % mod;
        b >>= 1;
        a = (a * a) % mod;
    }
    return res;
}
ll Det(ll n, ll _a[N][N])
{
    ll a[N][N];
    memcpy(a, _a, sizeof(a));
    bool flag = 0; ll res = 1;
    auto Swap = [&] (int x, int y) -> void {
        swap(a[x], a[y]); flag ^= 1;
    };
    for(int i = 1; i <= n; i++)
    {
        for(int j = i; j <= n; j++)
        {
            if(a[j][i])
            {
                if(i ^ j) Swap(i, j);
                break;
            }
        }
        for(int j = i + 1; j <= n; j++)
        {
            ll c = a[j][i] * qpow(a[i][i], mod - 2) % mod;
            for(int k = i; k <= n; k++)
                a[j][k] = (a[j][k] - c * a[i][k]) % mod;
        }
        res = (res * a[i][i]) % mod;
    }
    if(flag) res = -res;
    return (res % mod + mod) % mod;
}
void solve()
{
    cin >> n >> m;
    s = n + 1; t = n + 2;
    memset(a, 0, sizeof(a));
    legal.reset();
    int cnts = 0;
    for(int i = 1; i <= n; i++)
    {
        char c;
        cin >> c;
        if(c == 'S') add(s, i, 1), cnts++;
        else if(c == 'R') add(i, t, 1);
    }
    add(t, s, cnts);
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            char c;
            cin >> c;
            if(c - '0') add(i, j, 1);
        }
    }
    for(int i = 1; i <= n + 2; i++)
        if(a[i][i])
            legal[i] = 1;
    int tmpn = 0;    
    for(int i = 1, icnt = 0; i <= n + 2; i++)
    {
        if(!legal[i]) continue;
        icnt++; tmpn++;
        for(int j = 1, jcnt = 0; j <= n + 2; j++)
        {
            if(!legal[j]) continue;
            jcnt++;
            b[icnt][jcnt] = (a[i][j] % mod + mod) % mod;     
        }
    }
    ll res = Det(tmpn - 1, b);
    for(int i = 1; i <= n + 2; i++)
        if(a[i][i])
            res = (res * f[a[i][i] - 1]) % mod;
    res = (res * qpow(f[cnts], mod - 2)) % mod;
    res = (res * qpow(f[cnts - 1], mod - 2)) % mod;
    cout << res << "\n";
}
int main()
{
    //freopen("sample.in", "r", stdin);
    //freopen("sample.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    init();
    int T;
    cin >> T;
    while(T--) solve();
    return 0;
}

    参考资料

    • 1

    [USACO21OPEN] Routing Schemes P

    信息

    ID
    7037
    时间
    2000ms
    内存
    256MiB
    难度
    8
    标签
    递交数
    23
    已通过
    4
    上传者
    1. Language
    2. 兼容模式
    3. 主题
    3. Worker 0, 19ms
    4. Powered by Hydro v5.0.1 Community