解題區►解題區 - UVa

UVa 506 - System Dependencies

contents

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

Problem

參照《算法競賽入門經典》一書

軟體安裝時，會同時下載所需要的插件包，而插件包的軟體也有可能繼續安裝所需要的插件包。如此遞迴下去把所需要的元件都安裝好。

當安裝一個軟體時，分成使用者安裝和系統安裝兩種，使用者只能刪除自己安裝的軟體，其相依的插件包必須由系統來進行刪除，系統刪除時，會檢查是否還有其他軟體需要相依，若不存在相依，則會將此軟體刪除。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
DEPEND   TELNET TCPIP NETCARD
DEPEND TCPIP NETCARD
DEPEND DNS TCPIP NETCARD
DEPEND  BROWSER   TCPIP  HTML
INSTALL NETCARD
INSTALL TELNET
INSTALL foo
REMOVE NETCARD
INSTALL BROWSER
INSTALL DNS
LIST
REMOVE TELNET
REMOVE NETCARD
REMOVE DNS
REMOVE NETCARD
INSTALL NETCARD
REMOVE TCPIP
REMOVE BROWSER
REMOVE TCPIP
END

Sample Output

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
DEPEND   TELNET TCPIP NETCARD
DEPEND TCPIP NETCARD
DEPEND DNS TCPIP NETCARD
DEPEND  BROWSER   TCPIP  HTML
INSTALL NETCARD
   Installing NETCARD
INSTALL TELNET
   Installing TCPIP
   Installing TELNET
INSTALL foo
   Installing foo
REMOVE NETCARD
   NETCARD is still needed.
INSTALL BROWSER
   Installing HTML
   Installing BROWSER
INSTALL DNS
   Installing DNS
LIST
   NETCARD
   TCPIP
   TELNET
   foo
   HTML
   BROWSER
   DNS
REMOVE TELNET
   Removing TELNET
REMOVE NETCARD
   NETCARD is still needed.
REMOVE DNS
   Removing DNS
REMOVE NETCARD
   NETCARD is still needed.
INSTALL NETCARD
   NETCARD is already installed.
REMOVE TCPIP
   TCPIP is still needed.
REMOVE BROWSER
   Removing BROWSER
   Removing HTML
   Removing TCPIP
REMOVE TCPIP
   TCPIP is not installed.
END

Solution

一道模擬，假想一張 DAG 圖，刪除時暴力檢查其逆向的依存軟體是否存在。

使用 STL 和遞迴可以讓程式更簡單易懂。

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <stdio.h>
#include <map>
#include <queue>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;
vector<string> getArgs(char line[]) {
    stringstream sin(line);
    vector<string> ret;
    string token;
    while (sin >> token)
        ret.push_back(token);
    return ret;
}
map<string, int> name2id;
map<int, string> id2name;
map<int, vector<int> > dependInstall, invDependInstall;
map<int, int> installStatus;
vector<int> installList;
int getId(string s) {
    int &ret = name2id[s];
    if (ret == 0) {
        ret = (int) name2id.size();
        id2name[ret] = s;
    }
    return ret;
}
string getName(int id) {
    return id2name[id];
}
int isDepended(int id) {
    vector<int> &v = invDependInstall[id];
    for (int i = 0; i < v.size(); i++) {
        if (installStatus[v[i]])    return 1;
    }
    return 0;
}
void installSoft(int id, int top) {
    if (installStatus[id] == 0) {
        vector<int> &v = dependInstall[id];
        for (int i = 0; i < v.size(); i++)
            installSoft(v[i], 0);
        printf("   Installing %s\n", getName(id).c_str());
        installStatus[id] = top ? 1 : 2;
        installList.push_back(id);
    }
}
void removeSoft(int id, int top) {
    if ((top == 1 || installStatus[id] == 2) && !isDepended(id)) {
        installStatus[id] = 0;
        printf("   Removing %s\n", getName(id).c_str());
        vector<int> &v = dependInstall[id];
        for (int i = 0; i < v.size(); i++)
            removeSoft(v[i], 0);
        installList.erase(find(installList.begin(), installList.end(), id));
    }
}
int main() {
    char line[2048];
    while (gets(line)) {
        vector<string> args = getArgs(line);
        puts(line);
        if (args[0] == "DEPEND") {
            vector<int> softId;
            for (int i = 1; i < args.size(); i++) {
                softId.push_back(getId(args[i]));
            }
            vector<int> &v = dependInstall[softId[0]];
            for (int i = 1; i < softId.size(); i++) {
                v.push_back(softId[i]);
                invDependInstall[softId[i]].push_back(softId[0]);
            }
        } else if (args[0] == "INSTALL") {
            if (installStatus[getId(args[1])]) {
                printf("   %s is already installed.\n", args[1].c_str());
            } else {
                installSoft(getId(args[1]), 1);
            }
        } else if (args[0] == "REMOVE") {
            if (installStatus[getId(args[1])] == 0) {
                printf("   %s is not installed.\n", args[1].c_str());
            } else if (isDepended(getId(args[1]))) {
                printf("   %s is still needed.\n", args[1].c_str());
            } else {
                removeSoft(getId(args[1]), 1);
            }
        } else if (args[0] == "LIST") {
            for (int i = 0; i < installList.size(); i++) {
                printf("   %s\n", getName(installList[i]).c_str());
            }
        } else if (args[0] == "END") {
            break;
        }
    }
    return 0;
}
/*
 DEPEND   TELNET TCPIP NETCARD
 DEPEND TCPIP NETCARD
 DEPEND DNS TCPIP NETCARD
 DEPEND  BROWSER   TCPIP  HTML
 INSTALL NETCARD
 INSTALL TELNET
 INSTALL foo
 REMOVE NETCARD
 INSTALL BROWSER
 INSTALL DNS
 LIST
 REMOVE TELNET
 REMOVE NETCARD
 REMOVE DNS
 REMOVE NETCARD
 INSTALL NETCARD
 REMOVE TCPIP
 REMOVE BROWSER
 REMOVE TCPIP
 END
 */