반응형

문제 출처 :


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


알고리즘 분석 :


문제 해결에 필요한 사항

1. 네트워크 플로우

2. 애드몬드 카프 알고리즘


이 문제의 각 사람들은 몇가지의 돼지 우리 키를 가지고 있다.


이 키를 이용하여 문을 열고 돼지를 사고 난 후, 주인장은 돼지를 재분배하여 나중에 또 같은 키로 문을 여는 사람이있다면 그런 사람들에게 최대한 돼지를 많이 팔아야 하는 상황이다.


따라서 이 문제는 그래프 모델링을 다음과 같게 하면 쉽게 해결 할 수 있다.


바로 예제를 모델링해보자.



왼쪽의 1,2,3은 사람을 나타내고 오른쪽의 1`,2`,3`은 돼지 우리를 나타낸다.


검정색 간선으로만 그래프를 모델링하면 우리는 다음과 같은 요구사항을 놓치게 된다.

'종혁이는 팔고 남은 돼지들을 현재 열려져 있는 우리들을 상대로 재분배 할 수 있다.'


이를 위해 우리는 푸른색 간선을 추가하는데 푸른색 간선은 특정 키를 사람들이 공유하고 있다면 그것끼리 간선을 생성해주면 된다는 의미이다. 


예를들어 1,2번 사람은 1번키를 공유하기에 1,2번을 이어주고 1,3번 사람은 2번키를 공유하기에 1,3번을 이어준다.


그리고 이 문제는 순차적으로 1번 사람부터 돼지 우리를 방문하여 돼지를 사가는 것이므로 양방향 간선이 필요하지 않다.


결국 위와같이 그래프를 모델링하고 최대 유량을 구해주면 문제를 해결 할 수 있다.






소스 코드 : 


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
#include <iostream>
#include <cstdio>
#include <memory.h>
#include <queue>
#include <vector>
#include <algorithm>
 
#define fastio() ios::sync_with_stdio(0),cin.tie(0);
 
using namespace std;
 
const int INF = 987654321;
const int pig = 200;
 
int c[1500][1500], f[1500][1500];
vector<int> adj[1500];
 
int s = 0, t = 1300;
 
vector<int> share[1500];
 
int main()
{
    fastio();
 
    int n, m;
    cin >> m >> n;
 
    // source :: 0 sink :: 1300
    for (int i = 1; i <= m; i++)
    {
        int val;
        cin >> val;
 
        c[pig + i][t] = val;
        adj[pig + i].push_back(t);
        adj[t].push_back(pig + i);
 
    }
 
 
    for (int i = 1; i <= n; i++)
    {
        int key;
        cin >> key;
 
        for (int j = 0; j < key; j++)
        {
            int val;
            cin >> val;
 
            share[val].push_back(i);
 
            c[i][pig + val] = INF;
            adj[i].push_back(pig + val);
            adj[pig + val].push_back(i);
        }
 
        int val;
        cin >> val;
 
        c[0][i] = val;
        
        adj[0].push_back(i);
        adj[i].push_back(0);
    }
 
    for (int i = 1; i <= m; i++)
    {
        if (!share[i].size())
            continue;
 
        for (int j = 0; j < share[i].size() - 1; j++)
        {
            int here = share[i][j];
            for (int k = j + 1; k < share[i].size(); k++)
            {
                int next = share[i][k];
 
                c[next][here] = INF;
 
                adj[here].push_back(next);
                adj[next].push_back(here);
            }
        }
    }
 
    int totalFlow = 0;
 
    while (1)
    {
        vector<int> prev(1500, -1);
 
        queue<int> q;
        q.push(s);
 
        while (!q.empty() && prev[t] == -1)
        {
            int here = q.front();
            q.pop();
 
            for (int i = 0; i < adj[here].size(); i++)
            {
                int next = adj[here][i];
                if (prev[next] != -1)
                    continue;
 
                if (c[here][next] - f[here][next] > 0)
                {
                    q.push(next);
                    prev[next] = here;
                }
            }
        }
 
        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])
        {
        
            f[prev[i]][i] += flow;
            f[i][prev[i]] -= flow;
        }
        totalFlow += flow;
    }
 
    cout << totalFlow;
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus


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

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

[11066번] 파일 합치기  (0) 2017.11.16
[11495번] 격자 0 만들기  (2) 2017.11.15
[2866번] 문자열 잘라내기  (0) 2017.11.13
[9996번] 한국이 그리울 땐 서버에 접속하지  (0) 2017.11.13
[3024번] 마라톤 틱택토  (0) 2017.11.12

티스토리툴바