백준17643 Amusement Park

작성일 | In

문제 링크

  • http://icpc.me/17643

문제 출처

  • 2019 CEOI Day2 1번

사용 알고리즘

  • DP

시간복잡도

  • $O(3^N)$

풀이

주어진 간선으로 만들 수 있는 모든 DAG의 가중치의 합을 구하는 문제입니다.
DAG의 가중치는 각 간선의 가중치의 합으로 정의되고, 간선의 가중치는 입력으로 주어진대로 사용하면 0, 반대 방향으로 사용하면 1입니다.

Subtask 4 (63점, N ≤ 15)

DAG의 위상정렬은 유일하지 않을 수 있으니 유일한 순서를 정의하는 것이 편할 것 같습니다.
$ord(G)$ = Kahn’s Algorithm(BFS로 위상정렬하는 방법)의 각 단계에서, 선택할 수 있는 가장 작은 정점을 선택해서 얻은 순서로 정의합시다. 이렇게 정의하면 각 DAG $G$는 유일한 $ord(G)$를 갖습니다.

$D(A, B)$ = $ord(G)$의 prefix가 $A$의 순열이고, indegree가 0인 정점이 $B$인 DAG의 개수로 정의하면, 상태공간이 $O(4^N)$가지인 DP가 나옵니다.
상태전이는 $A$에 정점 $c$를 추가하는 것으로 생각하면 됩니다.
시간복잡도는 $O(N 4^N)$이지만, 실제로는 불가능한 상태가 꽤 많기 때문에 $N \leq 15$면 시간 내에 구할 수 있습니다.

어떤 순열 $P$가 DAG가 될 수 있다면 그 순열을 뒤집은(모든 간선의 방향을 뒤집은) $P^R$도 가능합니다. 그러므로 문제의 정답은 (DAG 경우의 수) × $\frac{M}{2}$입니다.
코드

Subtask 5 (100점, N ≤ 18)

위 풀이에서 $A$와 $B$가 disjoint함을 관찰하고 3진법을 사용하면 $O(N 3^N)$에 풀 수 있다는데 저는 구현을 못해서 다른 풀이를 짰습니다.

$D(i)$ = 집합 $i$에 있는 정점들로만 DAG를 만드는 경우의 수로 정의합시다.

DAG에는 indegree가 0인 정점이 몇 개 존재합니다.
$i$의 부분집합 $j$에 대해 $j$에 있는 모든 정점의 indegree가 0이라고 고정하면, $i \setminus j$로 만든 DAG에 $j$의 원소들을 붙여서 새로운 DAG를 만들 수 있습니다.
포함배제를 이용하면 $\displaystyle D(i) = \sum_{j \subset i, j \neq \emptyset} (-1)^{\vert j \vert + 1}dp[i \oplus j]$라는 점화식을 찾을 수 있습니다.

시간 복잡도는 $\displaystyle \sum_{i=0}^{N} {n \choose i}2^i$이므로 $O(3^N)$입니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
typedef pair<int, int> p;
const int mod = 998244353;

int n, m, cnt[1<<18];
bool g[22][22], chk[1<<18];
ll dp[1<<18];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> m;
    for(int i=0; i<m; i++){
        int s, e; cin >> s >> e; s--; e--;
        g[s][e] = g[e][s] = 1;
    }
    for(int i=0; i<(1<<n); i++){
        for(int j=0; j<n; j++) if(i & (1 << j)) {
            for(int k=j+1; k<n; k++) if(i & (1 << k)) {
                if(g[j][k]){ chk[i] = 1; break; }
            }
            if(chk[i]) break;
        }
    }

    dp[0] = 1;
    for(int i=1; i<(1<<n); i++) cnt[i] = cnt[i^(i&-i)] + 1;
    for(int i=1; i<(1<<n); i++){
        for(int j=i; j; j=(i&(j-1))) if(!chk[j]) {
            if(cnt[j] & 1) dp[i] += dp[i^j];
            else dp[i] = dp[i] -= dp[i^j];
            if(dp[i] < 0) dp[i] += mod;
            if(dp[i] >= mod) dp[i] %= mod;
        }
    }
    cout << dp[(1<<n)-1] * m % mod * (mod/2+1) % mod;
}