ABC041-D 徒競走

問題のリンク

問題概要

匹のうさぎの徒競走について、 のうさぎは のうさぎよりも先にゴールしたという情報が 個与えられる。

この時徒競走の順位として矛盾しないものの総数を求めよ。

解法

与えられる情報を有向グラフとして捉えると、トポロジカルソートの総数を求めよという問題に帰着される。

トポロジカルソートの数え上げは所謂bitDPで可能。

http://www-erato.ist.hokudai.ac.jp/docs/autumn2013/inoue.pdf

この解説がとても分かりやすかった。

実装方針としては、状態を0と1で管理（1:もう使った、0:まだ使ってない）し、矛盾がなければDPテーブルを更新していく。

実装

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long int ll;

bool bad[16][16];
ll dp[1<<16];
int main(){
    int n,m; cin >> n >> m;
    for(int i=0;i<m;i++){
        int x,y; cin >> x >> y;
        x--; y--;
        bad[y][x]=true;
    }
    dp[0]=1;
    for(int i=0;i<(1<<n);i++){
        for(int j=0;j<n;j++){
            if(!(1&(i>>j))){
                bool ok=true;
                for(int k=0;k<n;k++){
                    if(1&(i>>k)){
                        if(bad[k][j])ok=false;
                    }
                }
                if(ok){
                    dp[i+(1<<j)]+=dp[i];
                }
            }
        }
    }
    cout << dp[(1<<n)-1] << endl;
}