,
,
,
,
,
Link
===簡單的翻譯(不逐字翻了...字好多)
安裝軟體有很多依存關係，例如說你沒有TCPIP你就裝不起來TELNET。
所以如果明確(explicity)要裝TELNET，你會附帶地把TCPIP裝起來。
等你下次裝FTP(也需要TCPIP)時，就不用重裝一遍TCPIP。
但同樣的，在TELNET還裝著的情況下你不能把TCPIP移除。
有時候我們需要移除一些程式。為了省出更多空間，我們在移除某些程式時會把一些
只為了這個程式能正常運行才附帶安裝的檔案一起移除。
例如說如果我們為了裝TELNET而把TCPIP附帶裝起來，之後我們移除TELNET時發現，
TCPIP只是為了讓TELNET能正常運作而附帶安裝，TELNET移除後TCPIP將沒有存在的必要
便會順便將TCPIP解除安裝。
已經裝上的軟體不會再被安裝一遍(因為附帶而安裝的軟體不會因為再被安裝一遍而
變成明確要安裝的軟體)、已經移除的軟體也不能再被移除。
===
寫這題用到一堆C++的技巧xD
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <sstream>
#include <list>
#include <vector>
#include <string>
#include <map>
#define MAX 2510
//Converter
std::map<std::string, int> conv;
std::string rconv[MAX];
int ccnt;
//Answer List
std::list<int> ans;
std::list<int>::iterator it;
//Graph
std::vector<int> re[MAX], ee[MAX];
//DAG DP
int chneed[MAX], vst[MAX], ins[MAX], im[MAX];
//Parser
std::stringstream sin;
std::string buf;
inline int getno(std::string&b) {
int rtn = conv[b];
if(rtn == 0) {
ccnt ++;
conv[b] = ccnt;
rconv[ccnt] = b;
rtn = ccnt;
}
return rtn;
}
inline void insert(int np) {
ans.push_back(np);
ins[np] = true;
std::cout << " Installing " << rconv[np] << '\n';
}
void dfsI(int now) {
chneed[now] ++;
vst[now] ++;
for(int i=re[now].size()-1,nxt; i>=0; i--) {
nxt = re[now][i];
if(vst[nxt]) continue;
dfsI(nxt);
}
if(!ins[now]) {
ins[now] = true;
insert(now);
}
}
inline void remove(int np) {
ans.remove(np);
ins[np] = im[np] = false;
std::cout << " Removing " << rconv[np] << '\n';
}
void dfsR1(int now, int need) {
vst[now] = true;
chneed[now] -= need;
for(int i=re[now].size()-1,nxt; i>=0; i--) {
nxt = re[now][i];
if(vst[nxt]) continue;
dfsR1(nxt, need);
}
}
void dfsR2(int now) {
if(chneed[now]) return;
int can = true;
for(int i=ee[now].size()-1,nxt; i>=0; i--) {
nxt = ee[now][i];
if(ins[nxt]) {
can = false;
break;
}
}
if(!can) return;
remove(now);
for(int i=re[now].size()-1,nxt; i>=0; i--) {
nxt = re[now][i];
if(!ins[nxt]) continue;
dfsR2(nxt);
}
}
int main() {
while(true) {
getline(std::cin, buf);
std::cout << buf << '\n';
sin.clear();
sin.str(buf);
sin >> buf;
std::string ch, fa;
int nch, nfa;
switch(buf[0]) {
case 'D':
sin >> ch;
nch = getno(ch);
while(sin >> fa) {
nfa = getno(fa);
re[nch].push_back(nfa);
ee[nfa].push_back(nch);
}
break;
case 'I':
sin >> ch;
nch = getno(ch);
if(ins[nch]) {
std::cout << " " << ch << " is already installed.\n";
}
else {
memset(vst, 0, sizeof(vst));
im[nch] = true;
dfsI(nch);
}
break;
case 'R':
sin >> ch;
nch = getno(ch);
if(!ins[nch]) {
std::cout << " " << ch << " is not installed.\n";
}
else {
if(chneed[nch]>1 || (chneed[nch]==1 && !im[nch])) {
std::cout << " " << ch << " is still needed.\n";
}
else {
memset(vst, 0, sizeof(vst));
dfsR1(nch, im[nch]);
dfsR2(nch);
}
}
break;
case 'L':
for(it=ans.begin(); it!=ans.end(); it++) {
std::cout << " " << rconv[*it] << '\n';
}
break;
case 'E':
exit(0);
break;
}
}
}
//8966453 506 System Dependencies Accepted C++ 0.024 2011-06-19 06:57:53
