静かで孤独な日記

のんびりたまに

ABC041_D 徒競走

  • muzukasii...




pakapa104.hatenablog.com

  • ↑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;
}