0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

n!通りの全探索を学ぶ

Last updated at Posted at 2020-05-28

#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;
}

0
0
1

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
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?