很有意思的一道题。

首先我们分析题意,可以发现一个点只有一条出边,只有若干个环才能满足结构。

那么就要求入点都是不相同的,也就是枚举度数选择哪条出边,然后把集合并在一起,看看大小为不为 $n$

这个哈希可以做。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <iostream>
#define ull unsigned long long 
using namespace std;
const int N = 2e5 + 5;
const ull p1 = 13, p2 = 17, mod1 = 998244353, mod2 = 1e9 + 7;

map<ull, int> m1, m2;
vector<ull> V1[10], V2[10];
struct node {int x, y; node(int x = 0, int y = 0) : x(x), y(y){}};
bool cmp (const node &a, const node &b) {return a.y < b.y;}
vector<node> G[N];
vector<int> E[10][10];
ull pw1[N], pw2[N], h1[N], h2[N], n1, n2, c1[N], c2[N]; bool vis[N];
int deg[N], sta[N], nxt[N], prv[N], cnt[N], mid;

ull ksm(ull a, ull b, ull mod) {ull ans = 1; for (; b; b >>= 1, a = a * a % mod) if (b & 1) ans = ans * a % mod; return ans;} 

void dfs1(int i, ull w1, ull w2) {
    if (i == mid) {
        ++m1[w1]; ++m2[w2];
        return ;
    }
    i = prv[i]; int siz = V1[i].size();
    //if (!siz) return ;
    for (int j = 0; j < siz; ++j) 
        dfs1(i, (w1 + V1[i][j]) % mod1, (w2 + V2[i][j]) % mod2);
}

ull ans;

void dfs2(int i, ull w1, ull w2) {
    if (i == prv[mid]) {
        ull sub1 = ((n1 - w1 + (mod1 << 5))% mod1 + mod1) % mod1;
        ull sub2 = ((n2 - w2 + (mod2 << 5))% mod2 + mod2) % mod2;
        ans += min(m1[sub1], m2[sub2]);
        return; 
    }
    i = nxt[i]; int siz = V1[i].size();
    //if (!siz) return ;
    for (int j = 0; j < siz; ++j) 
        dfs2(i, (w1 + V1[i][j]) % mod1, (w2 + V2[i][j]) % mod2);
}

int main() {
    memset(deg, 0, sizeof deg);
    int n, m, k; scanf("%d%d%d", &n, &m, &k);
    pw1[1] = pw2[1] = 1; 
    for (int i = 2; i <= n; ++i) {
        pw1[i] = pw1[i - 1] * p1 % mod1;
        pw2[i] = pw2[i - 1] * p2 % mod2;
    }
    h1[1] = h2[1] = c1[1] = c2[1] = 1;
    for (int i = 2; i <= n; ++i) {
        c1[i] = i * pw1[i] % mod1; c2[i] = i * pw2[i] % mod2;
        h1[i] = (h1[i - 1] + c1[i]) % mod1;
        h2[i] = (h2[i - 1] + c2[i]) % mod2;
    }
    n1 = h1[n], n2 = h2[n]; 
    
    for (int i = 1; i <= m; ++i) {
        int x, y, w; scanf("%d%d%d", &x, &y, &w);
        G[x].push_back(node(y, w));
        ++deg[x];
    }
    for (int i = 1; i <= n; ++i) 
        ++cnt[deg[i]];
    int top = 0;
    for (int i = 1; i <= k; ++i) if (cnt[i])
        sta[++top] = i;
    mid = sta[top / 2 + 1];
    nxt[0] = sta[1]; prv[10] = sta[top];
    for (int i = 1; i <= top; ++i) 
        nxt[sta[i]] = i == top ? 10 : sta[i + 1],
        prv[sta[i]] = i == 1 ? 0 : sta[i - 1];
    
    for (int i = 1; i <= n; ++i) {
        int id = deg[i];
        sort(G[i].begin(), G[i].end(), cmp);
        int siz = G[i].size();
        for (int j = 0; j < siz; ++j) {
            E[id][j + 1].push_back(G[i][j].x);
        }
    }
    for (int i = 1; i <= k; ++i) if(cnt[i])
        for (int j = 1; j <= k; ++j) {
            for (int z = 1; z <= n; ++z) vis[z] = 0;
            sort(E[i][j].begin(), E[i][j].end());
            bool flag = 1; int siz = E[i][j].size();
            if (!siz) continue;
            for (int z = 0; z < siz; ++z) {
                if (vis[E[i][j][z]]) {flag = 0; break;}
                vis[E[i][j][z]] = 1;
            }
            if (!flag) continue;
            ull w1 = 0, w2 = 0; 
            for (int z = 0; z < siz; ++z) {
                w1 = (w1 + c1[E[i][j][z]]) % mod1;
                w2 = (w2 + c2[E[i][j][z]]) % mod2;
                
            }
            V1[i].push_back(w1);
            V2[i].push_back(w2);
        }
    ans = 0ull;
    dfs1(10, 0ull, 0ull);
    dfs2(0, 0ull, 0ull);
    for (int i = 1; i <= k; ++i) 
        if (!cnt[i]) ans *= i;
    printf("%llu\n", ans);
    return 0;
}