UVa 506 System Dependencies-编程实验室

题目描述

题目要求模拟软件组件的安装和移除过程。每个组件可能有依赖关系（必须预先安装其他组件）。安装命令可以显式或隐式安装组件，移除命令只能移除不再被需要的组件。需要根据命令执行相应的操作并输出结果。

输入格式

输入包含若干命令，每行一个命令。命令类型有：

DEPEND item1 item2 [item3 ...]：定义依赖关系，item1item1item1依赖于item2item2item2、item3item3item3等。
INSTALL item：安装itemitemitem及其依赖（若尚未安装）。
REMOVE item：移除itemitemitem（若未被其他组件依赖且不是显式安装）。
LIST：列出所有已安装的组件（按安装顺序）。
END：结束当前测试用例。

组件名称不超过101010个字符，区分大小写。依赖关系在INSTALL之前定义，无循环依赖。输入以END结束。

输出格式

对于每个命令，先原样输出命令本身。对于INSTALL和REMOVE，输出执行的动作（每行以三个空格开头）。对于LIST，输出所有已安装组件（每行以三个空格开头）。对于DEPEND和END，不输出额外内容。具体输出格式见样例。

样例

输入

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

输出

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

题目分析

本题的核心是维护组件的依赖关系和安装状态，模拟安装和移除过程。

数据结构

explicitly：记录显式安装的组件。
installed：记录已安装的组件及其安装序号。
sequence：按安装序号存储组件名称。
depend：每个组件的依赖列表。
referencedBy：每个组件被哪些组件依赖。

安装逻辑

递归安装组件的所有依赖（先依赖后自身）。
若组件已安装，则跳过。
显式安装的组件标记为显式。

移除逻辑

若组件未被任何其他组件依赖，且不是显式安装（或允许隐式移除），则可移除。
移除后，递归检查其依赖是否可移除。

命令处理

DEPEND：记录依赖关系。
INSTALL：若已安装则输出already installed，否则调用安装函数。
REMOVE：若未安装则输出not installed，若仍被需要则输出still needed，否则调用移除函数。
LIST：按安装顺序输出所有组件。

复杂度分析

每个命令处理复杂度O(依赖数)O(\text{依赖数})O(依赖数)，总复杂度可接受。

代码实现

// System referredencies// UVa ID: 506// Verdict: Accepted// Submission Date: 2017-04-25// UVa Run Time: 0.000s//// 版权所有（C）2017，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intindexer=0;// index of itemsmap<string,bool>explicitly;// explicitly installed itemsmap<string,int>installed;// installed items include explicitly and implicitlymap<int,string>sequence;// installed items with ordermap<string,vector<string>>depend;// item1 depends item2, item3, ...map<string,set<string>>referencedBy;// item1 referenced by item2, item3, ...voidinstall(string software,booltopmost){for(autocomponent:depend[software]){referencedBy[component].insert(software);install(component,false);}if(installed.find(software)==installed.end()){cout<<" Installing "<<software<<'\n';installed.insert(make_pair(software,indexer));sequence.insert(make_pair(indexer,software));indexer++;if(topmost)explicitly[software]=true;}}voidremove(string software,booltopmost){if((topmost||!explicitly[software])&&referencedBy[software].size()==0){cout<<" Removing "<<software<<'\n';sequence.erase(installed[software]);installed.erase(software);referencedBy.erase(software);if(topmost)explicitly[software]=false;for(autocomponent:depend[software]){referencedBy[component].erase(software);if(referencedBy[software].size()==0&&!explicitly[software])remove(component,false);}}}voidparse(string line){string action,software,component;istringstreamiss(line);iss>>action;if(action=="DEPEND"){iss>>software;while(iss>>component)depend[software].push_back(component);}elseif(action=="INSTALL"){iss>>software;if(installed.find(software)!=installed.end())cout<<" "<<software<<" is already installed.\n";elseinstall(software,true);}elseif(action=="REMOVE"){iss>>software;if(installed.find(software)==installed.end())cout<<" "<<software<<" is not installed.\n";else{if(referencedBy[software].size()>0)cout<<" "<<software<<" is still needed.\n";elseremove(software,true);}}elseif(action=="LIST"){for(autos:sequence)cout<<" "<<s.second<<'\n';}}intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);string line;while(getline(cin,line)){if(line!="END"){do{cout<<line<<'\n';if(line=="END")break;parse(line);}while(getline(cin,line));}indexer=0;explicitly.clear();installed.clear();sequence.clear();depend.clear();referencedBy.clear();}return0;}