題意：給定$n$個(gè)點(diǎn)$m$張圖的有向圖，有$1～m$互不相同每個(gè)點(diǎn)出度不超過(guò)$k$。對(duì)于一個(gè) $k$元組$c_i$，圖中的每個(gè)點(diǎn)$u$只保留第$c_{de{g}_u}$小的邊。求有多少種$c$使得在保留下來(lái)的圖中每個(gè)點(diǎn)沿著出邊一直往下走可以走回自己。

$n,m\le 2\times 10^5,k\le 9$

顯然直接$k!$暴力枚舉方案，問(wèn)題在于如何快速判斷。

不難看出題中的條件等價(jià)于每個(gè)點(diǎn)入度恰好為$1$

也相當(dāng)于每條邊的終點(diǎn)恰好遍歷$1～n$

寫(xiě)個(gè)哈希就完了

復(fù)雜度$O(n+k!)$

#include <iostream> #include <cstdio> #include <cstring> #include <cctype> #include <vector> #include <utility> #include <cstdlib> #include <ctime> #define MAXN 200005 using namespace std; int u[MAXN],v[MAXN],n,m,k; typedef pair<int,int> pi; vector<int> e[MAXN]; vector<pi> lis[MAXN]; inline int id(const pi& p){return p.first*(p.first-1)/2+p.second;} int ans[10],key[MAXN],val[10][10],rt,cnt; void check() {int t=0;for (int i=1;i<=k;i++) t+=val[i][ans[i]];if (t==rt) ++cnt; } void dfs(int i) {if (i>k) return check();for (ans[i]=1;ans[i]<=i;ans[i]++) dfs(i+1); } int main() {scanf("%d%d%d",&n,&m,&k);for (int i=1;i<=n;i++) rt+=(key[i]=rand());for (int i=1;i<=m;i++){int x,y,w;scanf("%d%d%d",&x,&y,&w);u[w]=x,v[w]=y;}for (int i=1;i<=m;i++) e[u[i]].push_back(v[i]);for (int u=1;u<=n;u++)for (int i=0;i<(int)e[u].size();i++)val[e[u].size()][i+1]+=key[e[u][i]];dfs(1);cout<<cnt;return 0; }

總結(jié)

以上是生活随笔為你收集整理的【CF1394B】Boboniu Walks on Graph【图论】【集合哈希】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。