반응형

문제 출처 :


https://www.acmicpc.net/problem/3640



알고리즘 분석 :


문제 해결에 필요한 사항

1. MCMF

2. 그래프 모델링


이 문제는 그래프 모델링에서 조심해야할 부분이 있다.


보통 edge를 구조체로 이용했다면 상관없지만, 배열로 flow, cost, capacity를 표현했다면 문제를 풀 수 없다.


왜냐면 cost를 넣는 과정에서 역방향 cost도 넣어주는데 이때 오류가 난다.


예를들어 a->b에 c를 넣으면 b->a는 -c를 넣게 된다. 이때 b->a로 d값을 넣는 인풋이 오면 a->b가 -d로 갱신된다.


따라서 이 문제 만큼은 edge 구조체를 이용하자.


S-시작정점-중간지점들-끝정점-T로 두면 문제를 해결 할 수 있다.


배는 2번 항해할 예정이니 시작, 끝정점의 듀얼노드는 capacity를 2로 준다.


그외 중간 지점들은 capacity를 1로 준다.


그 후 중간지점들 사이의 cost는 입력받는 값을 이용해준다. capacity = 1(겹치는 경로가 생기면 안되니)


마지막으로 S와 시작점, T와 끝점의 capacity를 2로 준다.


이제 MCMF를 돌려보자.










소스 코드 : 


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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
 
using namespace std;
 
const int INF = 987654321;
const int MAX_V = 2020;
const int S = MAX_V - 2;
const int T = MAX_V - 1;
 
struct Edge {
    int v, cost, capacity, flow, rev;
    Edge(int v, int cost, int c, int f, int rev)
        :v(v), cost(cost), capacity(c), flow(f), rev(rev) {}
};
 
vector<Edge> adj[MAX_V];
 
void addEdge(int here, int next, int cost, int cap)
{
    adj[here].emplace_back(next, cost, cap, 0, adj[next].size());
    adj[next].emplace_back(here, -cost, 0, 0, adj[here].size() - 1);
}
 
int main()
{
    int n, m;
    while (scanf("%d %d", &n, &m) != EOF)
    {
        for (int i = 0; i < MAX_V; i++)
            adj[i].clear();
 
        // 듀얼 노드간의 값 설정
        for (int i = 1; i <= n; i++)
        {
            if (i == 1 || i == n)
                addEdge(i, i + n, 0, 2);
            else
                addEdge(i, i + n, 0, 1);
        }
 
        for (int i = 0; i < m; i++)
        {
            int from, to, val;
            scanf("%d %d %d", &from, &to, &val);
 
            addEdge(from + n, to, val, 1);
        }
 
        addEdge(S, 1, 0, 2);
        addEdge(n, T, 0, 2);
 
        int result = 0;
 
        while(1)
        {
            int vPrev[MAX_V], ePrev[MAX_V], dist[MAX_V];
            bool inQ[MAX_V] = { 0 };
 
            queue<int> q;
            fill(vPrev, vPrev + MAX_V, -1);
            fill(ePrev, ePrev + MAX_V, -1);
            fill(dist, dist + MAX_V, INF);
 
            dist[S] = 0;
            inQ[S] = true;
 
            q.push(S);
 
            while (!q.empty())
            {
                int here = q.front();
                q.pop();
 
                inQ[here] = false;
 
                for (int i = 0; i < adj[here].size(); i++)
                {
                    int next = adj[here][i].v;
                    int c = adj[here][i].capacity;
                    int f = adj[here][i].flow;
                    int d = adj[here][i].cost;
 
                    if (c - f > 0 && dist[next] > dist[here] + d)
                    {
                        dist[next] = dist[here] + d;
                        vPrev[next] = here;
                        ePrev[next] = i;
 
                        if (!inQ[next])
                        {
                            q.push(next);
                            inQ[next] = true;
                        }
                    }
                }
            }
            if (vPrev[T] == -1)
                break;
 
            int flow = INF;
 
            for (int i = T; i != S; i = vPrev[i])
            {
                int prev = vPrev[i];
                int idx = ePrev[i];
                flow = min(flow, adj[prev][idx].capacity - adj[prev][idx].flow);
            }
 
            for (int i = T; i != S; i = vPrev[i])
            {
                int prev = vPrev[i];
                int idx = ePrev[i];
 
                result += adj[prev][idx].cost * flow;
 
                adj[prev][idx].flow += flow;
                adj[i][adj[prev][idx].rev].flow -= flow;
            }
        }
        printf("%d\n", result);
    }
 
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus


반응형
저작자표시 비영리 변경금지

'Applied > 알고리즘 문제풀이' 카테고리의 다른 글

[11585번] 속타는 저녁 메뉴  (0) 2017.12.11
[1495번] 기타리스트  (0) 2017.12.10
[11407번] 책 구매하기  (0) 2017.12.08
[8992번] 집기 게임  (0) 2017.12.07
[1544번] 사이클 단어  (0) 2017.12.07

티스토리툴바