CF 보충 문제 E. Boboniu Walks on Graph

E. Boboniu Walks on Graph
제목 링크
제목
방향 이 있 는 그림 을 주 고 그림 에서 걸 을 때 도 는 i 의 가장자리 이 고 변 권 크기 가 ci 의 작은 가장자리 에 만 갈 수 있 습 니 다. c 배열 이 몇 가지 가 있 는 지 물 어보 고 모든 점 을 만족 시 켜 야 합 니 다. 이 점 에서 걸 어가 면 이 점 으로 돌아 갈 수 있 습 니 다.매 점 의 입 도 는 모두 9 보다 작다.
해제
모두 이 점 으로 돌아 갈 수 있 지만 각 점 의 아웃 사 이 드 는 하나 밖 에 없 기 때문에 n 개의 점, 입 도 는 모두 1 이다.입 도 는 10 보다 작 기 때문에 c 배열 을 폭력 적 으로 매 거 한 다음 check 할 수 있 습 니 다.어떻게 확인 합 니까?매 거 진 c 배열 에 따라 가면 각 점 의 입 도 는 1 과 같 으 면 된다.따라서 i 로 읽 힌 모든 점 의 가중치 크기 가 j 일 때 어떤 점 까지 갈 수 있 는 지 미리 처리 할 수 있 습 니 다.처음 사용 한 bitset, 과감 한 tle.해시 로 바 꿨 으 면 좋 겠 다.

#include
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
typedef pair<int,ll> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
typedef unsigned long long ull;
typedef unordered_set<int>::iterator sit;
#define st first
#define sd second
#define mkp make_pair
#define pb push_back
void tempwj(){
     freopen("hash.in","r",stdin);freopen("hash.out","w",stdout);}
ll gcd(ll a,ll b){
     return b == 0 ? a : gcd(b,a % b);}
ll qpow(ll a,ll b,ll mod){
     a %= mod;ll ans = 1;while(b > 0){
     if(b & 1)ans = ans * a % mod;a = a * a % mod;b >>= 1;}return ans;}
struct cmp{
     bool operator()(const pii & a, const pii & b){
     return a.second > b.second;}};
int lb(int x){
     return  x & -x;}
//friend bool operator < (Node a,Node b)     
const int inf = INT_MAX;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9+7;
const int maxn = 2e5+10;
const int M = 1e6 + 2;
int temp[maxn];
int n,k;
// bitset flag;
// bitset ss;
// bitset val[10][10];
int key[maxn];
int val[10][10];
int ans =0 ;
int flag;
void dfs(int pos)
{
     
	if(pos > k)
	{
     
		// ss.reset();
		int ss = 0;
		for (int i = 1; i <= k; i ++ )
		{
     
			ss += val[i][temp[i]];
		}
		// if(ss == flag)
		// {
     
		// 	// for (int i = 1; i <= k; i ++ )
		// 	// {
     
		// 	// 	printf("%d ",temp[i]);
		// 	// }
		// 	// printf("  1111111
");
		// 	ans ++ ;
		// }
		if(ss == flag)
			ans ++ ;
		return;
	}
	for (int i = 1; i <= pos; i ++ )
	{
     
		temp[pos] = i;
		dfs(pos + 1);
	}
}
std::vector<pii> vv[maxn];
int du[maxn];
int main()
{
     
	int m;
	scanf("%d%d%d",&n,&m,&k);
	for (int i =1 ; i<= n; i ++ )
	{
     
		key[i] = rand();
		flag += key[i];
	}
	for (int i = 1; i <= m; i ++ )
	{
     
		int x,y,v;
		scanf("%d%d%d",&x,&y,&v);
		du[x] ++ ;
		vv[x].pb(mkp(v,y));
	}
	for (int i =1 ; i <= n; i ++ )
		sort(vv[i].begin(),vv[i].end());
	for (int i = 1; i <= n; i ++ )
	{
     
		for (int j = 0; j < vv[i].size(); j ++ )
		{
     
			val[du[i]][j + 1] += key[vv[i][j].sd];
		}
	}
	dfs(1);
	printf("%d
",ans);
}