문제: 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<int, int>> vt; int main(){ while (scanf("%d%d", &n, &m) != EOF) { if (!n&&!m)return 0; vt.clear(); memset(c, 0, sizeof(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 |