ABC041_D 徒競走
- muzukasii...
- ↑wakarimiga hukai !!!
http://www-erato.ist.hokudai.ac.jp/docs/autumn2013/inoue.pdf
- ↑naruhodo!!!
正直僕にはエディトリアルが何を言ってるのか分からなかった。
自分の頭はたしかに良くないのでググって調べてみたら、こんな僕にでもわかる記事があって助かりました。
以下コード
#include<bits/stdc++.h> #define ll long long #define fi first #define se second using namespace std; int n,m; ll dp[(1<<16)+10]; bool a[20][20]; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.precision(10); cout<<fixed; #ifdef LOCAL_DEFINE freopen("in", "r", stdin); freopen("out","w",stdout); #endif cin>>n>>m; for(int i=0;i<m;i++){ int to,from;cin>>from>>to; from--;to--; a[to][from]=1;//from->to } dp[0]=1; for(int i=0;i<(1<<n);i++){ bool b[20][20]; for(int j=0;j<n;j++)for(int k=0;k<n;k++)b[j][k]=a[j][k];//copy for(int j=0;j<n;j++){ if(i&(1<<j)){ for(int k=0;k<n;k++){ b[k][j]=0;//j->kの入次数を消す } } } for(int j=0;j<n;j++){//iにない頂点から入次数が0のものを探す旅に出る if(i&(1<<j))continue; bool flag=1; for(int k=0;k<n;k++){ if(b[j][k]){ flag=0; break; } } if(flag)dp[i|(1<<j)]+=dp[i]; } } cout<<dp[(1<<n)-1]<<"\n"; #ifdef LOCAL_DEFINE cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"; #endif return 0; }