반응형

문제 출처 :


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



알고리즘 분석 :


문제 해결에 필요한 사항

1. MCMF

2. 그래프 모델링


가로 선들과 세로 선들을 따로 생각해보자.


그리고 가로 선을 Source와 연결시키고 세로 선을 Sink와 연결, 마지막으로 가로와 세로가 맞닿은 부분이있다면 서로 연결하는 그래프를 생성해보자.


가로 선과 Source사이의 관계는 cost = 0, capacity = 1로 둔다.

세로 선과 Sink사이의 관계는 cost = 0, capacity = 1로 둔다.


이때 가로, 세로의 capacity = 1인 이유는 한번 이용하면 두 선분을 지우기 때문이다.


그후 가로와 세로에 대해 간선을 생성해주는데, 선분이 겹쳐져있는지 확인을 한 후, 겹쳐져있다면 두 선분 무게를 곱하고 음수로 넣어준다. 음수로 넣어야 최댓값을 구할 수 있기 때문이다.


마지막으로 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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <memory.h>
 
using namespace std;
 
const int MAX_V = 500;
const int S = MAX_V - 2;
const int T = MAX_V - 1;
const int sero = 200;
const int INF = 987654321;
 
typedef pair<int, int> pii;
vector<pair< pair<pii, pii>, pii> > width;
vector<pair<pii, int> > height;
 
vector<int> adj[MAX_V];
int c[MAX_V][MAX_V];
int f[MAX_V][MAX_V];
int d[MAX_V][MAX_V];
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while (tc--)
    {
        for (int i = 0; i < MAX_V; i++)
            adj[i].clear();
        width.clear();
        height.clear();
        memset(c, 0, sizeof(c));
        memset(f, 0, sizeof(f));
        memset(d, 0, sizeof(d));
 
        int n, m;
        scanf("%d %d", &n, &m);
 
        // S :: 498   T :: 499   가로 :: 0 ~ 199   세로 :: 200 ~ 399
        for (int i = 0; i < n; i++)
        {
            c[S][i] = 1;
            d[S][i] = 0;
            d[i][S] = 0;
 
            adj[S].push_back(i);
            adj[i].push_back(S);
        }
 
        for (int i = 0; i < m; i++)
        {
            c[i + sero][T] = 1;
            d[i + sero][T] = 0;
            d[T][i + sero] = 0;
 
            adj[i + sero].push_back(T);
            adj[T].push_back(i + sero);
        }
 
        // 가로
        for (int i = 0; i < n; i++)
        {
            int x1, y1, x2, y2, w;
            scanf("%d %d %d %d %d", &x1, &y1, &x2, &y2, &w);
 
            if (x1 > x2)
                swap(x1, x2);
            
            width.push_back({ {{x1,y1},{x2,y2}}, {i,w} });
        }
 
        // 세로
        for (int i = 0; i < m; i++)
        {
            int x1, y1, x2, y2, w;
            scanf("%d %d %d %d %d", &x1, &y1, &x2, &y2, &w);
 
            if (y1 > y2)
                swap(y1, y2);
            
            for (int j = 0; j < width.size(); j++)
            {
                int gx1 = width[j].first.first.first;
                int gy1 = width[j].first.first.second;
                int gx2 = width[j].first.second.first;
                int gy2 = width[j].first.second.second;
                int gidx = width[j].second.first;
                int gw = width[j].second.second;
 
                // 선분이 겹쳐져 있다면
                if(gx1 <= x1 && x1 <= gx2)
                    if (y1 <= gy1 && gy1 <= y2)
                    {
                        c[gidx][i + sero] = 1;
                        d[gidx][i + sero] = -gw * w;
                        d[i + sero][gidx] = gw * w;
                        adj[gidx].push_back(i + sero);
                        adj[i + sero].push_back(gidx);
                    }
            }
 
        }
 
 
        int result = 0;
        int cnt = 0;
 
        while (1)
        {
            int prev[MAX_V], dist[MAX_V];
            bool inQ[MAX_V] = { 0 };
 
            queue<int> q;
            fill(prev, prev + 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];
 
                    if (c[here][next] - f[here][next] > 0 && dist[next] > dist[here] + d[here][next])
                    {
                        dist[next] = dist[here] + d[here][next];
                        prev[next] = here;
 
                        if (!inQ[next])
                        {
                            q.push(next);
                            inQ[next] = true;
                        }
                    }
 
                }
            }
 
            if (prev[T] == -1)
                break;
 
            int flow = INF;
 
            for (int i = T; i != S; i = prev[i])
                flow = min(flow, c[prev[i]][i] - f[prev[i]][i]);
            
            for (int i = T; i != S; i = prev[i])
            {
                result += flow * d[prev[i]][i];
                f[prev[i]][i] += flow;
                f[i][prev[i]] -= flow;
            }
 
            cnt+=flow;
        }
 
        printf("%d %d\n", cnt, -result);
 
    }
    return 0;
}
 
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus


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

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

[3640번] 제독  (0) 2017.12.09
[11407번] 책 구매하기  (0) 2017.12.08
[1544번] 사이클 단어  (0) 2017.12.07
[11405번] 책 구매하기  (0) 2017.12.06
[3980번] 선발 명단  (0) 2017.12.06

티스토리툴바