Minimums on the Edges 풀이

최근에 푼 문제 중 가장 재미있는 것 같아서 풀이를 기록해둔다.

 

Link: www.acmicpc.net/problem/18664

18664번: Minimums on the Edges

$N$개의 정점이 있고, $M$개의 간선 $(u_1, v_1), \cdots, (u_M, v_M)$ 이 있는 그래프 $G$가 주어진다. (루프는 없고, parallel edge는 있을 수 있다.) 그래프의 정점들에 총 $S$개의 토큰을 놓아 다음 식의 값을 최대화 하는 문제이다. (단, $c(i)$는 정점 $i$위에 놓인 토큰의 수를 의미한다.)

$$ \sum_{i=1}^M \min(c(u_i), c(v_i)) $$

단, $N \le 18, M \le 100000, S \le 100$ 이다.

 

관점을 바꾸어 보면, 토큰을 다음과 같은 과정을 거쳐 차례로 놓는다고 생각할 수 있다.

 

• 토큰을 $1$개 이상 놓을 정점들에 토큰을 하나씩 놓는다.
• 토큰을 $2$개 이상 놓을 정점들에 토큰을 하나씩 놓는다.
• ...
• 토큰을 $S$개 이상 놓을 정점들에 토큰을 하나씩 놓는다.

각 시행에서 토큰을 놓은 정점 집합을 $V_1, V_2, \cdots, V_S$라 하면, $V_1 \supseteq V_2 \supseteq \cdots \supseteq V_S$가 된다. 그리고, 이 경우 문제의 답은 $\sum |E(G[V_i])|$가 된다. ($G[X]$는 $G$의 induced subgraph on $X$를 의미한다.)

 

$f: 2^{[N]} \to \mathbb{Z}$를 $f(X) = |E(G[X])|$로 해서 정의하자. 각 $1 \le i \le N$에 대해, $S_i$를 다음과 같이 정의하자:

$$ S_i = \arg\max_{|X| = i} f(X).$$

문제의 답부터 말하자면, 크기 $S$인 가방에 크기가 $i$이고, 값어치가 $f(S_i)$인 상품들을 넣는 냅색 문제로 이 문제를 환원하여 해결할 수 있다. 그리고 이의 정당성은 submodularity에서 나온다.

 

문제 제한이 작으므로, naive하게 $O(2^N \cdot N^2 + NS)$ 정도에 해결해주면 된다.