传送门

题意

给定一个n个点m条边的有向图，每一个点的出度最多为k，然后给你一个跑图规则数组ci，对于出度为x的点，跑当前点第cx小的边。问你有多少种数组c，可以使得对于任何点，总能沿着数组c跑，跑回该点。

思路

根据规则转换一下，对于所有点，它的出边都是固定的。所以每一个都在且仅在一个有向环内，即所有点都仅经过一次。可以看到k<=9,因此我们枚举所有的c数组，符合条件的计上。跑图的过程用点权hash来计算。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
#define maxn 100005
#define mod 1000000007
ll s[maxn<<1][2],node[maxn<<1],sum[10][10],n,m,k,per[maxn],ans=0,res=0;
vector<ll> G[maxn<<1];
int vis[maxn];
void check(){
    ll cnt=0;
    for(int i=1;i<=k;i++)
        cnt+=sum[i][per[i]];
    if(ans==cnt) res++;
}
void dfs(int x){
    if(x>k){
        check();
		return; 
    }
    for(int i=1;i<=x;i++){
		per[x]=i;
	    dfs(x+1);
	}
	return;
}

int main(){
    ll i,j,t,u,v,w;
    scanf("%lld%lld%lld",&n,&m,&k);
    for(i=1;i<=m;i++){
        scanf("%lld%lld%lld",&u,&v,&w);
        s[w][0]=u,s[w][1]=v;
    }
    for(i=1;i<=m;i++) G[s[i][0]].push_back(s[i][1]);
    for(i=1;i<=n;i++) node[i]=rand()%mod,ans+=node[i];
    for(i=1;i<=n;i++)
        for(j=0;j<G[i].size();j++)
            sum[G[i].size()][j+1]+=node[G[i][j]];
    dfs(1);
    printf("%lld\n",res);
}