블로그 옮겼습니다

UVa OJ 11765 - Component Placement 본문

Algorithm/Problem Solving

UVa OJ 11765 - Component Placement

sgc109 2017. 6. 26. 14:53

N개의 컴포넌트들이있고 판떼기가 하나있다. 판떼기는 앞면과 뒷면이있다. 각 컴포넌트를 

판떼기에 모두 붙이고싶은데 하나의 컴포넌트를 앞면에 붙이는 비용과 뒷면의 붙이는 비용은 다르고

각 컴포넌트마다도 비용이 또 다르다.

그리고 특정 컴포넌트들은 무조건 앞면 혹은 뒷면에 부착해야 된다는 조건이 주어진다.

-1 이면 뒷면에, 1이면 앞면에 붙여야하며 0이면 어떤면에 붙여도 상관없다는 것이다.

그리고 M개의 제한이 주어지는데 각 제한의 내용은 특정 두 컴포넌트를 다른 면에 붙였을 때에는

추가적인 비용이 발생한다는 것이다.  각 제한마다 두 컴포넌트와 추가 비용은 다르다.

이 때 N개의 컴포넌트를 모두 판떼기에 붙이는 최소 비용을 구하여라.


이 문제는 min-cut 문제이다. source -> 컴포넌트 -> sink 와 같은 식으로 N개의 컴포넌트들에 대해

그래프를 구성해주는데 source -> 컴포넌트 를 잇는 에지의 용량은 앞면에 붙이는 비용으로,

컴포넌트 -> sink 를 잇는 에지의 용량은 뒷면에 붙이는 비용으로 하여 max-flow 를 구하면

min-cut 이 되면서 cut 된 엣지가 source -> 컴포넌트 냐, 컴포넌트 -> sink 이냐에 따라 

최소 비용으로 컴포넌트를 붙이기 위해 앞면에 붙여야하는지 뒷면에 붙여야하는지를 알 수가 있다.


그렇다면 특정 컴포넌트를 무조건 앞면(or 뒷면)에 붙여야 한다는 조건은 어떻게 반영할까?

예를 들어 컴포넌트 C를 무조건 앞면에 붙여야 한다면 컴포넌트 -> sink 는 절대 cut 되면 안되고

source -> 컴포넌트 는 무조건 cut 되어야 한다는 의미이다. 그러면 그냥 컴포넌트 -> sink 에지의

용량을 무한대로 주면 절대로 cut 되지 않게 되면서 조건을 만족하게 된다.


그럼 M개의 제한은 어떻게 만족할까? 아래의 그림을 보자.


만약 컴포넌트1과 컴포넌트2 사이의 제한이 존재한다고 해보자. 그러면 만약 컴포1과 컴포2 사이에

간선을 이어주면, 컴포1은 윗면에 붙이고 컴포2는 아랫만에 붙인일 때에 이 간선을 무조건 cut하게 될 것이다.

그렇기 때문에 컴포1과 컴포2사이에 간선을 양 방향 둘다 용량을 비용으로 주면서 만들어 주고

max-flow를 구하면 자동으로 이 추가 비용도 감안하여 최소 컷, 즉 최소 비용을 구할 것이다.



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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int inf = 0x3c3c3c3c;
const long long infl = 0x3c3c3c3c3c3c3c3c;
 
int T,N,M;
int a;
vector<int> G[205];
int cap[205][205];
int par[205];
void connect(int a, int b, int c){
    G[a].push_back(b);
    G[b].push_back(a);
    cap[a][b] = c;
}
 
ll edmonds(int s, int t){
    ll ret = 0;
    while(1){
        memset(par,-1,sizeof(par));
        queue<int> q;
        q.push(s);
        par[s] = s;
        while(!q.empty() && par[t] == -1){
            int here = q.front();
            q.pop();
            for(int there : G[here]){
                if(cap[here][there] == 0 || par[there] != -1continue;
                par[there] = here;
                q.push(there);
            }
        }
        if(par[t] == -1break;
        int minFlow = inf;
        for(int p = t ; p != s; p = par[p]) minFlow = min(minFlow, cap[par[p]][p]);
        for(int p = t ; p != s; p = par[p]) cap[par[p]][p] -= minFlow, cap[p][par[p]] += minFlow;
        ret += minFlow;
    }
    return ret;
}
int main() {
    int S = 201, E = 202;
    cin >> T;
    for(int t = 1 ; t <= T; t++){
        memset(cap,0,sizeof(cap));
        for(int i = 0 ; i < 205; i++) G[i].clear();
        cin >> N >> M;
        for(int i = 0 ; i < N; i++){
             cin >> a;
             connect(S, i, a);
        }
        for(int i = 0 ; i < N; i++){
             cin >> a;
             connect(i, E, a);
        }
        for(int i = 0 ; i < N; i++){
             cin >> a;
             if(a == -1) cap[S][i] = inf;
             else if(a == 1) cap[i][E] = inf;
        }
        for(int i = 0 ; i < M; i++){
            int a, b, c;
            cin >> a >> b >> c;
            a--, b--;
            connect(a, b, c);
            cap[b][a] = c;
        }
        cout << edmonds(S, E) << endl;
    }
    return 0;
}
cs


Comments