티스토리 뷰

알고리즘 관련/UVaOJ

UVaOJ)10968 KuPellaKeS

JASON 자손9319 2017. 6. 20. 19:03

문제: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1909


도시가 주어질 때 연결 된 도시의 개수가 홀수개인 도시들을 몇개의 다리를 파괴하여 전부 2이상의 짝수개의 정점만 연결되게 만들어주려고 할 때 제거해야하는 최소 간선의 개수를 출력하는 문제이다.


연결 된 도시의 간선이 홀수인 정점이 2개 이하라는 조건도 있다.


우선 연결 된 도시의 간선이 홀수개인 정점이 두개가 있다고 생각해보자.


그렇다면 우리는 두 도시에 연결 된 간선을 하나씩 지워줘야 한다. 이 때 하나씩 지우면 반대쪽 정점들의 간선의 개수가 홀수가 되기 때문에 또 지워줘야한다. 이렇게 서로 지우다가 한 간선에서 만나게 되면 답을 만족하게 된다.


하지만 우리는 최소 간선의 개수를 구해야 하므로 그냥 두 도시의 최단거리를 구한다음에 삭제해주면 된다.


두 정점의 최단거리는 BFS를 통하여 구할 수 있다.


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
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
int n, m, x, y, disc[1010], g[1010], back[1010];
vector<vector<int>> vt;
int bfs(int here) {
    disc[here] = 1;
    queue<int> qu;
    qu.push(here);
    int ret = 0;
    while (qu.size()) {
        int qs = qu.size();
        while (qs--) {
            int h = qu.front();
            qu.pop();
            if (h != here&&g[h] % 2) {
                int bt = h;
                while (bt!=here) {
                    g[bt]--;
                    g[back[bt]]--;
                    bt = back[bt];
                }
                return ret;
            }
            for (auto next : vt[h]) {
                if (disc[next])continue;
                if (g[next] % && g[next] >= 3) {
                    qu.push(next);
                    disc[next] = 1;
                    back[next] = h;
                }
                if (!(g[next] % 2&& g[next] >= 4) {
                    qu.push(next);
                    disc[next] = 1;
                    back[next] = h;
                }
                
            }
        }
        ret++;
    }
    return -1;
}
int go() {
    for (int i = 1; i <= n; i++)
        if (g[i] < 2)return -1;
    int ret = 0;
    for (int i = 1; i <= n; i++) {
        if (g[i] % 2) {
            memset(disc, 0sizeof(disc));
            int f = bfs(i);
            if (f == -1)return -1;
            ret += f;
        }
    }
    return ret;
}
int main() {
    while (scanf("%d%d"&n, &m) != EOF) {
        if (!n&&!m)return 0;
        memset(g, 0sizeof(g));
        vt.clear();
        vt.resize(n + 1);
        for (int i = 0; i < m; i++) {
            scanf("%d%d"&x, &y);
            vt[x].push_back(y);
            vt[y].push_back(x);
            g[x]++, g[y]++;
        }
        int r = go();
        if (r == -1)puts("Poor Koorosh");
        else printf("%d\n", r);
    }
    return 0;
}
 
cs


'알고리즘 관련 > UVaOJ' 카테고리의 다른 글

UVaOJ)12159 Gun Fight  (0) 2017.06.27
UVaOJ)12878 Flowery Trails  (0) 2017.06.23
UVaOJ)10968 KuPellaKeS  (0) 2017.06.20
UVaOJ)12645 Water Supply  (0) 2017.06.19
UVaOJ)11751 Installing Diagnostic Software  (0) 2017.06.19
UVaOJ)12460 Careful teacher  (0) 2017.06.17
TAG
댓글
댓글쓰기 폼