UVA-506 系统依赖 题解答案代码 算法竞赛入门经典第二版

GitHub - jzplp/aoapc-UVA-Answer: 算法竞赛入门经典 例题和习题答案 刘汝佳 第二版

1. 如果一个已经隐式安装的组件又被显式安装，那么是否需要将这个组件的状态变更为显示安装？

不需要。

2. 题目的样例有一点错误。最后的HTML和TCPIP的卸载顺序反了。

3. 有题目没给数据范围，实测10000可以AC。

#include<string>
#include<string.h>
#include<map>
#include<vector>
#include<iostream>
#include<sstream>
#include<algorithm>
#define MAXN 10000
using namespace std;
int n;
map<string, int> mpName;
string vecName[MAXN];
vector<int> vecDepend[MAXN];
vector<int> vecDepend2[MAXN];
int vecInstall[MAXN];
vector<int> vecList;
int getNum(const string & word) {
if(mpName.count(word)) {
return mpName[word];
}
vecName[++n] = word;
mpName[word] = n;
return n;
}
void handleDepend(stringstream & ss) {
string word;
ss >> word;
int num = getNum(word);
int num2;
while(ss >> word) {
num2 = getNum(word);
vecDepend[num].push_back(num2);
vecDepend2[num2].push_back(num);
}
}
void installNum(int num, int type) {
int i;
for(i = 0; i < vecDepend[num].size(); ++i) {
if(!vecInstall[vecDepend[num][i]]) {
installNum(vecDepend[num][i], 1);
}
}
vecInstall[num] = type;
vecList.push_back(num);
cout <<
"
Installing " << vecName[num] << endl;
}
void handleInstall(const string & word) {
int num = getNum(word);
if(vecInstall[num]) {
cout << "
" << word << " is already installed." << endl;
return;
}
installNum(num, 2);
}
void removeListNum(int num) {
vecList.erase(find(vecList.begin(), vecList.end(), num));
}
void removeNum(int num) {
int i;
for(i = 0; i < vecDepend2[num].size(); ++i) {
if(vecInstall[vecDepend2[num][i]]) {
return;
}
}
vecInstall[num] = 0;
removeListNum(num);
cout << "
Removing " << vecName[num] << endl;
for(i = 0; i < vecDepend[num].size(); ++i) {
if(vecInstall[vecDepend[num][i]] == 1) {
removeNum(vecDepend[num][i]);
}
}
}
void handleRemove(const string & word) {
int num = getNum(word);
int i;
if(!vecInstall[num]) {
cout << "
" << word << " is not installed." << endl;
return;
}
for(i = 0; i < vecDepend2[num].size(); ++i) {
if(vecInstall[vecDepend2[num][i]]) {
cout << "
" << vecName[num] << " is still needed." << endl;
return;
}
}
vecInstall[num] = 0;
removeListNum(num);
cout << "
Removing " << vecName[num] << endl;
for(i = 0; i < vecDepend[num].size(); ++i) {
if(vecInstall[vecDepend[num][i]] == 1) {
removeNum(vecDepend[num][i]);
}
}
}
void handleList() {
int i;
for(i = 0; i < vecList.size(); ++i) {
cout << "
" << vecName[vecList[i]] << endl;
}
}
int main() {
string com;
string line, word;
n = 0;
memset(vecInstall, 0, sizeof(vecInstall));
while(getline(cin, line)) {
cout << line << endl;
stringstream ss(line);
ss >> com;
if(com[0] == 'D') {
handleDepend(ss);
}
else if(com[0] == 'I') {
ss >> word;
handleInstall(word);
}
else if(com[0] == 'R') {
ss >> word;
handleRemove(word);
}
else if(com[0] == 'L') {
handleList();
}
else if(com[0] == 'E') {
break;
}
}
return 0;
}

最后我遇到一个小坑，和题目无关的：

如果定义了一个有返回值的函数，却没有return语句，我的本地（DevC++）不会报错，一切正常。但是到了环境上却Runtime error。

一开始我以为是我代码遇到某些数据会会出错，找了好久，最后发现是这个问题。

最后

以上就是兴奋鱼为你收集整理的UVA-506 系统依赖 题解答案代码 算法竞赛入门经典第二版的全部内容，希望文章能够帮你解决UVA-506 系统依赖 题解答案代码 算法竞赛入门经典第二版所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。