L2-3 智能护理中心统计

标签：结点 EAST ZJ 管理 护理 智能 指令 L2 老人

题目描述：

智能护理中心系统将辖下的护理点分属若干个大区，例如华东区、华北区等；每个大区又分若干个省来进行管理；省又分市，等等。我们将所有这些有管理或护理功能的单位称为“管理结点”。现在已知每位老人由唯一的一个管理结点负责，每个管理结点属于唯一的上级管理结点管辖。你需要实现一个功能，来统计任何一个管理结点所负责照看的老人的数量。   注意这是一个动态问题，即随时可能有老人加入某个管理结点，并且老人是有可能从一个管理结点换到另一个管理结点去的。   输入格式： 输入在第一行中给出 2 个正整数：N（≤10^4 ）是老人的总数量，即老人们从 1 到 N 编号；M（≤10^5 ）是归属关系的总数。   接下来是 M 行，每行给出一对归属关系，格式为：   A B 表示 A 归属于 B。A 或 B 如果是某个管理结点，则用不超过 4 个大写英文字母表示其名称；如果是某位老人，则用老人的编号表示。这里每个 A 保证只有唯一的上级归属 B，且只有这个中心系统本身是没有上级归属的。此外，输入保证没有老人自己承担管理结点的角色，即 B 一定是一个管理结点，不可能是老人的编号。但一个管理结点既可以管辖下级结点，也可以直接护理一部分老人。   随后每行给出一个指令，格式为：   指令 内容 如果 指令 为 T，则表示有老人要入院或转院，内容 是某老人的编号和要去的管理结点的名称，以空格分隔；如果 指令 为 Q，则 内容 是一个管理结点的名称，意思是统计这个结点所负责照看的老人的数量；如果 指令 为 E，则表示输入结束。题目保证指令总数不会超过 100 个。   输出格式： 对每个 T 指令，将对应的老人转存到对应的管理结点名下；对每个 Q 指令，在一行中输出对应管理结点所负责照看的老人的数量。读到 E 指令就结束程序。   输入样例： 10 23 EAST CNTR ZJ EAST SD EAST WEST CNTR SX WEST HZ ZJ JN SD 2 JN 8 JTH 6 XAHP 4 ZDYH 5 ZDYH ZDYH HZ HUZ ZJ JX ZJ 1 JX 3 JN WZ ZJ XAHP XIAN XIAN SX YL SX JTH XIAN 7 XAHP Q EAST T 1 YL Q EAST Q SX T 8 ZDYH Q HZ Q HUZ T 10 XAHP Q CNTR E 输出样例： 5 4 4 3 0 9 代码实现：

#include<iostream>
#include<unordered_map>
#include<vector>
#include<queue>
using namespace std;
unordered_map<string,string>father;
unordered_map<string,vector<string> >mp;
unordered_map<string,int>num;
int n,m;
int bfs(string s){
	queue<string>q;
	q.push(s);
	//sum用来存储管理结点s的管理老人数量 
	int sum=0;
	//只要队列中还有结点就继续 
	while(q.size()){
		string s1=q.front();//获取当前管理结点 
		q.pop();
		sum+=num[s1];//加上当前结点的管理老人数量
		//搜索当前管理结点的子节点 
		for(int i=0;i<mp[s1].size();i++){
			q.push(mp[s1][i]);
		} 
	}
	//返回管理结点s的管理老人数量
	return sum;
}
int main(){
	cin>>n>>m;
	while(m--){
		string a,b;
		cin>>a>>b;
		//如果a是管理结点 
		if(a[0]>='A'&&a[0]<='Z'){
			//将a加入管理结点b中去
			mp[b].push_back(a);
		}else{
			//如果a是老人
			//将老人的父节点设为管理节点b 
			father[a]=b;
		 	//将管理结点b的管理老人数量加1 
		 	num[b]++;
		} 
	}
	char c;
	while(cin>>c){
		if(c=='E')break;
		string a,b;
		if(c=='T'){
			//如果老人要转院或入院 
			 cin>>a>>b;
			 //如果老人有父节点，将父节点的管理老人数量减1
			 if(father[a]!="")num[father[a]]--; 
			 //将老人的父节点设置为b
			 father[a]=b;
			 //将管理节点b的管理老人数量加1 
			 num[b]++;
		}else if(c=='Q'){
			//如果要统计管理结点管理老人数量 
			cin>>a; 
			cout<<bfs(a)<<endl;
		}
	}
	return 0;
} 

 

标签：结点,EAST,ZJ,管理,护理,智能,指令,L2,老人
From： https://www.cnblogs.com/hxss/p/17334230.html