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



이분매칭으로 문제를 해결했습니다.


문제해결방법

1. 인풋으로 들어온 상어의 능력치 별로 간선을 만들어줍니다.

a가 b를 먹을 수 있다면 a의 간선에 b를 넣어줍니다.

이 문제의 핵심은 a==b인 경우입니다.(세 개의 능력치가 같은 경우)

이게 왜 중요하냐면

a가 b를 먹었는데

밑에서 b가 a를 또 먹을 수 있기 때문에 이것을 방지해야합니다.


가장 간단한 방법으로(사실 다른 방법따위 모름) 인덱스가 a < b인 경우에만 먹을 수 있게 하면 됩니다.(물론 같은경우에만)

이렇게 되면 a와 b가 능력치가 같을경우 a를 처리할떄 b를 먹을 것이고 b를 처리할 때는 a > b 이므로 먹을 수 없습니다.


2. 간선을 만든 후 상어는 각각 두마리씩 먹을 수 있습니다. 그러므로 한번 처리할떄 두번씩 먹어줍니다 

제가 계속 실수 했던 부분이

visit을 초기화안하고 먹고 또먹었습니다.


이렇게

1
2
3
4
5
6
    for (int i = 0; i < n; i++) {
        memset(visit, 0, sizeof(visit));
        f(i);
        memset(visit, 0, sizeof(visit));
        f(i);
    }

cs


이렇게 멤셋을 두번해줘야합니다!!!
이유는 아래의 예시를 보면서 설명하겠습니다.

이 그림은 현재
1번이 1번과 2번을 매칭했을 때
2번이 1번을 뺏어서 1번이 3번과 매칭된 상황입니다.
2번이 1번을 뺏으면서 visit[1]은 방문한 상태가 되겠죠??
근데 visit초기화를 안하면
2번이  2번에 매칭을 시도하면서 1번으로 들어가서 1-2를 미뤄내고 4번에 연결되어야하는데(1과 4사이에 선이 있다고 가정)
이미 방문했기 때문에 그냥 넘어가버리게 되죠!@

이게 핵심입니당!!

3. 마지막으로 B배열이 -1인 것을 카운트하여 출력하면 정답입니다.(-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
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string.h>
#include <queue>
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <stack>
 
#define ll long long
#define INF 987654321
#define MOD 1000000
#define MAX_SIZE 1000
 
using namespace std;
 
int B[MAX_SIZE];
bool visit[MAX_SIZE];
vector<int> edge[MAX_SIZE];
 
int sharkSize[MAX_SIZE];
int sharkIntel[MAX_SIZE];
int sharkSpeed[MAX_SIZE];
 
int n;
 
int eat(int a, int b) {
    int ret = 0;
    if (sharkSize[a] < sharkSize[b]) return 0;
    else if(sharkSize[a] == sharkSize[b]) ret++;
    if (sharkIntel[a] < sharkIntel[b]) return 0;
    else if (sharkIntel[a] == sharkIntel[b]) ret++;
    if (sharkSpeed[a] < sharkSpeed[b]) return 0;
    else if (sharkSpeed[a] == sharkSpeed[b]) ret++;
 
    if (ret == 3) return 2;
    return 1;
}
 
bool f(int from) {
    visit[from] = 1;
 
    for (int i = 0; i < edge[from].size(); i++) {
        int to = edge[from][i];
        if (B[to] == -1 || !visit[B[to]] && f(B[to])) {
            B[to] = from;
            return 1;
        }
    }
 
    return 0;
}
 
 
int main() {
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        scanf("%d %d %d", &sharkSize[i], &sharkIntel[i], &sharkSpeed[i]);
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int eatFlag = eat(i, j);
 
            if (eatFlag == 1) edge[i].push_back(j); //먹을 수 있는경우
            else if (eatFlag == 2 && i < j) edge[i].push_back(j); // 능력치가 같은 경우
        }
    }
 
    memset(B, -1, sizeof(B));
    
    for (int i = 0; i < n; i++) {
        memset(visit, 0, sizeof(visit));
        f(i);
        memset(visit, 0, sizeof(visit));
        f(i);
    }
 
    int ret = 0;
    for (int i = 0; i < n; i++) if (B[i] == -1) ret++;
    printf("%d", ret);
 
    return 0;
}
cs





'알고리즘 > 네트워크 플로우' 카테고리의 다른 글

[12843] 복수전공  (0) 2017.08.24
[1017] 소수 쌍  (0) 2017.06.27
[6086] 최대유량  (1) 2017.06.03

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



처음엔 이분 매칭 문제인 것을 모르고..

엄청나게 틀렸네요... 시간초과 + 구현실수....


알고나서도 한참을 해맸는데요!

첫번째 이유는 첫번째 수와 매칭되는 수를 출력한다는 점이었어요..


소수 쌍을 구하는 것이기 때문에

홀수 + 홀수 = 짝수(2를 제외하고는 무조건 소수가 안됨)

짝수 + 짝수 = 짝수(무조건 안됨)

홀수 + 짝수 = 홀수(가능성 있음)

입니다!


그렇기 때문에 그룹을 홀수와 짝수로 나누어야하는데요!


첫번쨰 수가 홀수일수 도있고 짝수일 수도 있기 때문에 어떻게 진행해야할지 난해했습니다.

두번째 소수를 구하는 방법입니다. 풀고나니깐 뭐.. 에라토스테네스의 체를 써도 되고 그냥 나눠서 확인해도

입력받는 수가 1000까지기 때문에 최대 1999(두 수를 합쳐야하므로)밖에 안되서 오래걸리진 않습니다.


마지막으로 출력입니다. 입력이 정렬되서 들어온다는 말은 없으므로 출력할 때 정렬을 해야합니다.

저같은 경우는 우선순위 큐에 넣어서 그냥 큐가 빌때까지 출력했습니다.

-1이 출력되는 조건은 큐가 비어있다면 -1을 출력했습니다.


문제 해결 전략은

1. 첫번째 수와 다른 그룹의 수와 매칭을 시킨다.

2. 1에서 매칭된 수가 소수라면 1에서 매칭된 쌍을 제외하고 이분매칭 알고리즘을 이용해서 나머지를 매칭합니다.

3. 만약 전부 매칭해서 매칭 된 수가 입력 받은 N의 절반이 된다면 전부 매칭된 것이므로 우선순위 큐에다가 처음에 첫번째 수와 매칭한 수를 푸시해줍니다.

4. 위의 과정을 다른 그룹의 수의 개수만큼 반복합니다.


아래는 코드입니다.

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
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string.h>
#include <queue>
#include <iostream>
#include <algorithm>
#include <vector>
 
#define ll long long
#define MAX_SIZE 50
#define INF 987654321
#define MOD 1000000
using namespace std;
 
int arrA[MAX_SIZE];
int arrB[MAX_SIZE];
int pick;
int idxA, idxB;
 
int matchA[MAX_SIZE];
int matchB[MAX_SIZE];
bool visit[MAX_SIZE];
 
bool isPrime(int a) {
    if (a == 1) return 0;
    else if (a != 2 && a % 2 == 0) return 0;
    
    for (int i = 3; i * i <= a; i += 2) {
        if (a % i == 0) return 0;
    }
 
    return 1;
}
 
bool f(int idx) {
    if (visit[idx]) return 0;
    visit[idx] = 1;
 
    for (int i = 0; i < idxB; i++) {
        if (i == pick) continue;
 
        if (isPrime(arrA[idx] + arrB[i]) && (matchB[i] == -1 || !visit[matchB[i]] && f(matchB[i]))) {
            matchB[i] = idx;
            matchA[idx] = i;
 
            return 1;
        }
    }
 
    return 0;
}
 
int main() {
    int arr[MAX_SIZE];
    int n;
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
    
    for (int i = 0; i < n; i++) {
        if (arr[0] % 2 == arr[i] % 2) arrA[idxA++] = arr[i];
        else arrB[idxB++] = arr[i];
    }
 
    priority_queue<int> pq;
 
    for (int i = 0; i < idxB; i++) {
        if (isPrime(arrA[0] + arrB[i])) {
            pick = i;
            
            int cnt = 1;
            memset(matchA, -1, sizeof(matchA));
            memset(matchB, -1, sizeof(matchB));
 
            for (int j = 1; j < idxA; j++) {
                memset(visit, 0, sizeof(visit));
                if (f(j)) cnt++;
            }
 
            if (cnt == n / 2) pq.push(-arrB[i]);
        }
    }
 
    if (pq.empty()) puts("-1");
    else {
        while (!pq.empty()) {
            printf("%d ", -pq.top()), pq.pop();
        }
    }
 
    return 0;
}
cs


'알고리즘 > 네트워크 플로우' 카테고리의 다른 글

[12843] 복수전공  (0) 2017.08.24
[1671] 상어의 저녁식사  (0) 2017.07.02
[6086] 최대유량  (1) 2017.06.03

+ Recent posts

티스토리툴바