Theorem 3.4.의 알고리즘에서 가중치 있는 Matroid intersection의 경우에는 I 내부의 정점에 음의 가중치를 부여하고 나머지 정점에 양의 가중치를 부여해서 가장 가중치가 큰 경로를 찾고, 그 중 가장 적은 정점을 지나는 경로를 선택하면 풀 수 있다고 한다. 증명은 모른다.
'알고리즘' 카테고리의 다른 글
| 선형 시간의 Range Minimum Query (0) | 2018.10.25 |
|---|---|
| IOI18 meetings (1) | 2018.10.06 |
| Dynamic Connectivity in Graph (6) | 2017.10.02 |
| IOI16 Aliens (10) | 2017.10.01 |
