解題區/解題區 - UVa

UVa 11751 - Installing Diagnostic Software

contents

  1. 1. Input Format
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

You have recently been appointed as the administrator for a wired network of devices. Unfortunately, your predecessor used very poor quality lines to connect the devices. The board of executives is currently deciding if they want to fund an upgrade to a wireless network, or simply replace the existing wires with ones of better quality. As expected, this decision is being weighed down with bureaucratic nonsense; it looks like it will take some time before anything is approved.

Meanwhile, you still have to deal with the problem at hand. You have access to an antiquated version of Newton Network Monitor which is a software package that, once installed on a machine, will monitor all lines connected to that machine and immediately alert the user when a line has failed. This should help reduce your response time to any failures.

Your task is to install the software on some machines so each line is being monitored by at least one of its endpoint devices. For various technical reasons, the time it takes to install the software varies from device to device so you want to minimize the total amount of time spent installing the software. You cannot install on more than one machine at a time (since you only have one copy of the software) meaning the total time spent installing the software is exactly the sum of the installation times on each machine.

Input Format

Each input case begins with two numbers n,m with 1 ≤ n ≤ 1,000 and 0 ≤ m ≤ 25,000. Following this are m pairs of distinct integers between 0 and n-1 which describe a wire connecting the two devices. The time spent installing the software on machine numbered i is 2i. The input is terminated with n = m = 0; this should not be processed.
Output Format

For each input case, there is to be one line of output containing a sequence of n bits with no spaces. The i’th bit is 1 if the software is installed on machine i, and 0 if not.

Sample Input

1
2
3
4
5
6
3 2
0 2
1 2
3 1
1 2
0 0

Sample Output

1
2
110
010

Solution

題目描述：

給定一個 N 個點的城市和邊，每一條邊上至少有一個點安裝服務，而在編號 i 的地方設置服務器成本為 $2^{i}$，求最少花費。

題目解法：

明顯地，會發現對於編號最大的節點來說，周遭的點數全設置也不會比該點設置來得高，那還不如將周圍都設置服務。藉此，從編號大的開始檢查，如果還沒有設置服務，將其鄰居全都設置服務！

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
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <string.h>
using namespace std;
vector<int> g[1024];
int main() {
    int n, m, x, y;
    while(scanf("%d %d", &n, &m) == 2 && n + m) {
        for(int i = 0; i < n; i++)
            g[i].clear();
        for(int i = 0; i < m; i++) {
            scanf("%d %d", &x, &y);
            g[x].push_back(y);
            g[y].push_back(x);
        }
        int used[1024] = {};
        for(int i = n - 1; i >= 0; i--) {
            if(used[i])	continue;
            for(int j = 0; j < g[i].size(); j++)
                used[g[i][j]] = 1;
        }
        for(int i = 0; i < n; i++)
            printf("%d", used[i]);
        puts("");
    }
    return 0;
}