본문 바로가기

알고리즘 관련/UVaOJ

UVaOJ)11751 Installing Diagnostic Software

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


확실한 번역은 모르겠지만 대략적인 설명은 간선이 주어질 때 해당 간선에 연결 된 두정점중 하나는 반드시 소프트웨어가 설치되어야 할 때 최소비용으로 소프트웨어를 설치하는 방법을 출력하는 문제이다.


소프트웨어 설치비용은 i번 정점의 경우 2^i의 비용이 소모된다.


즉 i번 정점에 소프트웨어를 설치하는건 0~i-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
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
int n, m, x, y, c[1002];
vector<pair<intint>> vt;
int main(){
    while (scanf("%d%d"&n, &m) != EOF) {
        if (!n&&!m)return 0;
        vt.clear();
        memset(c, 0sizeof(c));
        for (int i = 0; i < m; i++) {
            scanf("%d%d"&x, &y);
            vt.push_back({ min(x,y),max(x,y) });
        }
        sort(vt.rbegin(), vt.rend());
        for (auto next : vt) {
            if (!c[next.first] && !c[next.second])
                c[min(next.first, next.second)] = 1;
        }
        for (int i = 0; i < n; i++)
            printf("%d", c[i]);
        puts("");
    }
    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)12460 Careful teacher  (0) 2017.06.17