例题6-21 系统依赖(System Dependencies, ACMICPC World Finals 1997, UVa506)

xiaoxiao2021-02-28  16

STL函数remove的用法: Transforms the range [first,last) into a range with all the elements that compare equal to val removed, and returns an iterator to the new end of that range. #include <iostream> #include <string> #include <vector> #include <stack> #include <queue> #include <deque> #include <set> #include <map> #include <algorithm> #include <sstream> #include <utility> #include <cstring> #include <cstdio> #include <cstdlib> #include <ctime> #include <cmath> #include <cctype> #define CLEAR(a, b) memset(a, b, sizeof(a)) #define IN() freopen("in.txt", "r", stdin) #define OUT() freopen("out.txt", "w", stdout) #define LL long long #define maxn 10005 #define maxm 200005 #define mod 1000000007 #define INF 1000000007 #define eps 1e-5 #define PI 3.1415926535898 #define N 26 using namespace std; //-------------------------CHC------------------------------// vector<string> names; map<string, int> id; vector<int> before[maxn], after[maxn]; vector<int> installed; int status[maxn]; int ID(string s) { if (id.count(s)) return id[s]; names.push_back(s); return id[s] = names.size() - 1; } void install(int u) { for (int i = 0; i < before[u].size(); ++i) install(before[u][i]); if (!status[u]) { status[u] = 2; cout << " Installing " << names[u] << endl; installed.push_back(u); } } bool needed(int u) { bool ret = false; for (int i = 0; i < after[u].size(); ++i) { if (status[after[u][i]]) ret = true; } return ret; } void remove(int u) { status[u] = 0; installed.erase(remove(installed.begin(), installed.end(), u), installed.end()); cout << " Removing " << names[u] << endl; for (int i = 0; i < before[u].size(); ++i) { int v = before[u][i]; if (status[v] == 2 && !needed(v)) remove(v); } } int main() { //IN(); OUT(); string in; while (getline(cin, in)) { cout << in << endl; if (in[0] == 'E') break; stringstream ss(in); string op; string name; ss >> op; if (op[0] == 'L') { for (int i = 0; i < installed.size(); ++i) cout << " " << names[installed[i]] << endl; } else { ss >> name; int u = ID(name); if (op[0] == 'D') { while (ss >> name) { int v = ID(name); before[u].push_back(v); after[v].push_back(u); } } else if (op[0] == 'I') { if (status[u]) cout << " " << name << " is already installed.\n"; else { install(u); status[u] = 1; } } else if (op[0] == 'R') { if (status[u] == 0) cout << " " << name << " is not installed.\n"; else if (needed(u)) cout << " " << name << " is still needed.\n"; else remove(u); } } } return 0; }
转载请注明原文地址: https://www.6miu.com/read-1150293.html

最新回复(0)