search
LoginSignup
0

More than 1 year has passed since last update.

posted at

updated at

n!通りの全探索を学ぶ

AtCoder 版!蟻本 (初級編)

今日からAtCoder 版!蟻本 (初級編)の記事を読み進めましょう!
蟻本とはプログラミングコンテストチャレンジブックの事です。
この本を読み進めてAtCoderに類似する問題があれば挑戦していきます。

特殊な状態の列挙

n! 通りの全探索を行う事です。
C++には「next_permutation」があります。

サンプル1

C++
#define MAX_N 100
bool used[MAX_N];
int perm[MAX_N];

void permutation(int pos, int n){
    if(pos == n){
        /* ここにpermの処理を書く */

        return;
    }

    for(int i=0; i<n; i++){
        if(!used[i]){
            perm[pos] = i;
            used[i] = true;
            permutation(pos+1, n);
            used[i] = false;
        }
    }
}

サンプル2

C++
#include<algorithm>
int perm[MAX_N];

void permutation(int n){
    for(int i=0; i<n; i++){
        perm[i]=i;
    }
    do{
        /* ここにpermの処理を書く */
    }while(next_permutation(perm, perm+n));
}

枝刈り

探索しなくても解が存在しない条件がある分岐からは処理を行わない。

問題

ABC 054 C One-stroke Path

問題文はAtCoderを参照してください。

  • 無向グラフを使います。
C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<cmath>
#include<cstdio>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384

using namespace std;
using ll =long long;
using P = pair<int,int>;

#include<algorithm>
#define MAX_N 8
bool G[MAX_N][MAX_N] = {false};
int order[MAX_N];

void permutation(int n){
    for(int i=0; i<n; i++){
        order[i]=i;
    }

    int res=0;
    do{
        if(order[0] != 0) continue;
        bool ok=true;
        /* ここにpermの処理を書く */
        for(int i=0; i+1<n; i++){
            int from = order[i];
            int to = order[i+1];

            if(!G[from][to]) ok=false;
        }
        if(ok) res++;
    }while(next_permutation(order, order+n));

    cout << res << endl;
}

int main(int argc, const char * argv[]) {
    int n, m;
    cin >> n >> m;

    rep(i, m){
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        G[a][b]=true;
        G[b][a]=true;
    }

    permutation(n);

    return 0;
}

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
What you can do with signing up
0