티스토리 뷰

문제: 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)11751 Installing Diagnostic Software  (0) 2017.06.19
UVaOJ)12460 Careful teacher  (0) 2017.06.17
댓글
댓글쓰기 폼