백준21639 Cooking

작성일 | In

문제 링크

  • http://icpc.me/21639

사용 알고리즘

  • 일반 그래프 매칭

시간복잡도

  • $O((\sum A_i)^3)$

풀이

매번 정확히 2개의 음식을 요리할 때, 최소 시간으로 $i$번째 음식을 $A_i$번 만들어야 합니다.
$i$번째 음식을 나타내는 정점을 $A_i$개 만든 뒤, $i$번째 음식과 $j$번째 음식을 비용이 $C(i, j)$인 간선으로 연결한 그래프를 생각해 봅시다. 이 그래프에서 가중치가 최소인 완전 매칭을 찾는다면, 그 매칭의 가중치가 정답이 될 것 입니다.

정점이 $V$개인 그래프의 최대/최소 가중치 매칭은 $O(V^3)$에 구할 수 있으므로 문제를 $O((\sum A_i)^3)$ 시간에 해결할 수 있습니다.
제가 갖고 있는 라이브러리는 최대 가중치 매칭만 구할 수 있기 때문에, 적당히 큰 값에서 원래 가중치를 뺀 그래프에서 최대 가중치 매칭을 구했습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
int N, M, A[11], ID[555], C[11][11];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1; i<=N; i++) cin >> A[i];
    for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) cin >> C[i][j];
    for(int i=1; i<=N; i++) for(int j=1; j<=A[i]; j++) ID[++M] = i;
    matching::init(M);
    for(int i=1; i<=M; i++) for(int j=1; j<=M; j++) if(i != j) matching::add_edge(i, j, 101010 - C[ID[i]][ID[j]]);
    auto [cost, match] = matching::solve();
    cout << (match * 2 == M ? 101010LL * match - cost : -1);
}