如何看自己网站流量,wordpress 页面路由,企业网站建设 百度文库,网站开发的pc或移动端题意#xff1a;给定nnn个点mmm张图的有向图#xff0c;有1∼m1\sim m1∼m互不相同每个点出度不超过kkk。对于一个 kkk元组cic_ici#xff0c;图中的每个点uuu只保留第cdeguc_{deg_u}cdegu小的边。求有多少种ccc使得在保留下来的图中每个点沿着出边一直往下走可以走回…题意给定nnn个点mmm张图的有向图有1∼m1\sim m1∼m互不相同每个点出度不超过kkk。对于一个 kkk元组cic_ici图中的每个点uuu只保留第cdeguc_{deg_u}cdegu小的边。求有多少种ccc使得在保留下来的图中每个点沿着出边一直往下走可以走回自己。
n,m≤2×105,k≤9n,m\leq 2\times 10^5,k\leq 9n,m≤2×105,k≤9
显然直接k!k!k!暴力枚举方案问题在于如何快速判断。
不难看出题中的条件等价于每个点入度恰好为111
也相当于每条边的终点恰好遍历1∼n1 \sim n1∼n
写个哈希就完了
复杂度O(nk!)O(nk!)O(nk!)
#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 pairint,int pi;
vectorint e[MAXN];
vectorpi lis[MAXN];
inline int id(const pi p){return p.first*(p.first-1)/2p.second;}
int ans[10],key[MAXN],val[10][10],rt,cnt;
void check()
{int t0;for (int i1;ik;i) tval[i][ans[i]];if (trt) cnt;
}
void dfs(int i)
{if (ik) return check();for (ans[i]1;ans[i]i;ans[i]) dfs(i1);
}
int main()
{scanf(%d%d%d,n,m,k);for (int i1;in;i) rt(key[i]rand());for (int i1;im;i){int x,y,w;scanf(%d%d%d,x,y,w);u[w]x,v[w]y;}for (int i1;im;i) e[u[i]].push_back(v[i]);for (int u1;un;u)for (int i0;i(int)e[u].size();i)val[e[u].size()][i1]key[e[u][i]];dfs(1);coutcnt;return 0;
}
