題目鏈接：
https://vjudge.net/PRoblem/31990/origin
題目大意：
模擬安裝軟件，分顯式好隱式安裝兩種情況。安裝一個(gè)軟件的時(shí)候，指明安裝的就是顯式安裝。 比如：
INSTALL A
這里A是顯示安裝，如果A必須要B和C軟件的支持的話，順便安裝上B和C，這里B和C就是隱式安裝上的。
然后是刪除軟件，刪除的時(shí)候以遞歸的形式刪除，先刪除指明安裝的軟件，然后刪除這個(gè)軟件的支持軟件，但是如果支持軟件是顯式安裝上的話，就不刪除了。
INSTALL B INSTALL A REMOVE A
這里的B就不會(huì)被刪除，安裝A時(shí)同時(shí)安裝的C會(huì)被刪除掉。此外如果A的支持軟件是另一個(gè)軟件的支持軟件的話，也不會(huì)被刪除掉。
解題過程：
題目本身不難，有是一個(gè)復(fù)雜的模擬題，書上給了些提示和代碼，對(duì)比著，寫出來不難。 需要映射下軟件的名字，這里用到了之前 UVA-12096 里面的映射方法。
題目分析：
先把字符串名稱用MAP映射成整數(shù)，容易處理些。 安裝和刪除的函數(shù)，注意遞歸處理。 把depend的輸入分離的時(shí)候使用stringstream處理。
題目不難，不過用到了好多有用的方法，這里Mark下。
AC代碼：
#include<bits/stdc++.h>using namespace std;const int MAX = 112345;map<string, int> nameList;vector<string> getName, nameTable;string str;vector<int> depend1[MAX], depend2[MAX];int status[MAX];string blank = " ";int ID(string name){ if (nameList.count(name)) return nameList[name]; getName.push_back(name); return nameList[name] = getName.size()-1;}void depend(){ stringstream ss; string item_name; int item1, item2; ss << str; ss >> item_name; ss >> item_name; item1 = ID(item_name); while (ss >> item_name) { item2 = ID(item_name); depend1[item1].push_back(item2); depend2[item2].push_back(item1); }}void install(int item, bool topLevel){ if (!status[item]) { for (int i = 0; i < depend1[item].size(); i++) install(depend1[item][i], false); string item_name = getName[item]; cout << blank << "Installing " << item_name << endl; nameTable.push_back(item_name); status[item] = topLevel? 1:2; } else if (topLevel) cout << blank << getName[item] << " is already installed." << endl;}void list_(){ for (int i = 0; i < nameTable.size(); i++) cout << blank << nameTable[i] << endl;}bool needed(int item){ for (int i = 0; i < depend2[item].size(); i++) if (status[depend2[item][i]]) return true; return false;}void remove_(int item, bool topLevel){ string item_name = getName[item]; if (status[item] == 0 && topLevel) { cout << blank << item_name << " is not installed." << endl; return; } if (!needed(item) && (status[item] == 2 || topLevel)) { status[item] = 0; for (int i = 0; i < nameTable.size(); i++) { if (nameTable[i] == item_name) { nameTable.erase(nameTable.begin()+i); break; } } cout << blank << "Removing " << item_name << endl; for (int i = 0; i < depend1[item].size(); i++) remove_(depend1[item][i], false); } else if (topLevel) cout << blank << item_name << " is still needed." << endl;}int main(){// freopen("in","r",stdin); while(getline(cin, str)) { cout << str << endl; if (str[0] == 'D') { depend(); } if (str[0] == 'I') { stringstream ss; ss << str; string item_name; ss >> item_name; ss >> item_name; int item = ID(item_name); install(item, true); } if (str[0] == 'E') { break; } if (str[0] == 'R') { stringstream ss; ss << str; string item_name; ss >> item_name; ss >> item_name; int item = ID(item_name); remove_(item, true); } if (str[0] == 'L') { list_(); } }}
