본문 바로가기

Computer Science/Algorithms & Problem Solving

Minimums on the Edges 풀이

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

 

Link: www.acmicpc.net/problem/18664

 

18664번: Minimums on the Edges

Print n numbers a1, a2, . . . , an (0 ≤ ai ≤ s), where ai is the number of tokens you put on the i-th vertex. The sum of printed integers must be equal to s. The sum of capacities of all edges must be the maximum possible. If there are multiple optimal

www.acmicpc.net

$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)$ 정도에 해결해주면 된다.

'Computer Science > Algorithms & Problem Solving' 카테고리의 다른 글

Minimums on the Edges 풀이  (0) 2020.10.19
최대 부분합과 쿼리  (0) 2020.06.06
Kruskal's Algorithm과 MST의 성질  (0) 2020.03.13