Yukicoder090 品物の並び替え

問題概要

ここに0番〜(N-1)番の品物がある。
また、 $item1$ $item2$ $score$ という形式で書かれた得点表がある。
品物を並べた時、item1がitem2よりも前であればscore点を獲得できるという意味である。

得点表が与えられるので、品物を適切に並び替えた時、獲得できる得点を最大化したい。そのときの得点を出力せよ。

$N\leqq9$、$M\leqq N*(N-1)$、$item1,item2 < N$、$1≦score≦10^4$

yukicoder090

解法

$N!$が間に合うので全探索する。

計算量:$O(N!M)$

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using VS = vector<string>;    using LL = long long;
    using VI = vector<int>;       using VVI = vector<VI>;
    #define ALL(a)  begin((a)),end((a))
    #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
    
    LL ans = 0LL;
    
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        int N, M; cin >> N >> M;
        using tp = tuple<int, int, int>;
        vector<tp>rules(M);
        FOR(i, 0, M) {
            int a, b, c; cin >> a >> b >> c;
            rules[i] = tp(a, b, c);
        }
    
        VI a(N, 0);
        iota(ALL(a), 0);
    
        do {
            LL ret = 0;
            VI b(N);
            FOR(j, 0, N) {
                b[a[j]] = j;
            }
            for (tp& rule : rules) {
    
                int x, y, z; tie(x, y, z) = rule;
                if (b[x] < b[y]) {
                    ret += z;
                }
            }
    
            ans = max(ans, ret);
        } while (next_permutation(ALL(a)));
    
        cout << ans << "\n";
    
        return 0;
    }