CCF 区块链 80分

左手的ㄟ右手 2023-07-09 09:30 7阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTE1Njg2_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTE1Njg2_size_16_color_FFFFFF_t_70 1][]

[完全参照他的博客，他的能满分，但是我的超时，只能80分。][80][https://blog.csdn.net/qq\_26873647/article/details/104273455][80]

#include<iostream>
    #include<algorithm>
    #include<string>
    #include<vector>
    #include<queue>
    #include<map>
    #include<unordered_map>
    #include<set>
    #include<sstream>
    using namespace std;
    const int MAXN = 502; 
    
    int t;  //传输延迟 
    vector<int> adj[MAXN];   //邻接表实现的地图 
    vector<int> links[MAXN]; //节点维护的主链 
    map<int,unordered_map<int,vector<int> > > create;  //map<a,unordered_map<b,c> ：a时刻b节点新增的块集合c 
    map<int,unordered_map<int,vector<int> > > receive; //map<a,unordered_map<b,c> ：a时刻b节点收到的相邻节点的最优主链 
    
    //获取输入，因为输入可能是三个数字也可能是两个数字，所以使用istringstream
    vector<int> getInput(){  
    	string str;
    	getline(cin,str);
    	istringstream input(str);
    	vector<int> ans;
    	int res = -1;
    	while(input>>res){
    		ans.push_back(res);
    	}
    	return ans;
    }
    
    void update(int time,int nid,vector<int> &vec){
    	vector<int> &cur = links[nid];
    	//主链长度<更新链长度，或者主链长度==更新链长度，但是更新链最后一个块编号更小。 
    	if(cur.size() < vec.size() || (cur.size()==vec.size() && vec.back() < cur.back()) ){
    		cur = vec;  //将主链替换为更新链，因为是引用，cur改变时，links[nid]也改变了。 
    		//向我的相邻节点传送我刚刚更新过的主链。 
    		for(int i=0;i<adj[nid].size();i++){
    			int u = adj[nid][i];  //取出相邻节点的编号
    			//如果我发送的主链比其他节点发送的主链好，就把u节点在time+t时刻的最优更新链替换成我的。 
    			if(receive[time+t][u].size() < cur.size() 
    				|| (receive[time+t][u].size()==cur.size() && cur.back() < receive[time+t][u].back()) ){
    				receive[time+t][u] = cur; 
    			} 
    		} 
    	}
    }
    
    void processUntil(int time){
    	auto crep = create.begin();
    	auto recp = receive.begin();
    	//按照时刻进行遍历 
    	while(crep!=create.end() || recp!=receive.end()){ 
    		if(crep==create.end() || (recp!=receive.end() && recp->first <= crep->first)){  //先接收更新链 
    			if(recp->first > time){
    				break;
    			}
    			//遍历在该时刻下每一个节点收到的相邻节点发送的最优的更新链  {节点编号 : 更新链}
    			for(auto ele=recp->second.begin();ele!=recp->second.end();ele++){
    				//ele->first : 节点编号 。  ele->second：更新链
    				//更新 (在recp->first时刻，ele.first节点有了一个更新链ele->second)
    				update(recp->first,ele->first,ele->second); 
    			}
    			recp = receive.erase(recp);
    		}else if(crep!=create.end()){  //再增加块 
    			if(crep->first > time){
    				break;
    			} 
    			//遍历在该时刻下的所以节点的新增块集合。 map集合的键值对为{节点编号：新增块集合}
    			for(auto ele=crep->second.begin();ele!=crep->second.end();ele++){
    				//ele->first : 节点编号 。  ele->second：新增块集合
    				vector<int> temp = links[ele->first];
    				//在原主链的基础上追加新增的块结合 
    				temp.insert(temp.end(),ele->second.begin(),ele->second.end());
    				//更新 (在crep->first时刻，ele.first节点有了一个更新链temp)
    				update(crep->first,ele->first,temp); 
    			} 
    			crep = create.erase(crep);  //把crep迭代器对应的空间删除，返回下一个迭代器的位置。
    			//下面一行是关键点：我将详细介绍
    			/*
    			** 假设我们第一次进入循环时，任意节点都没有收到来自相邻节点的更新链。
    			** 则我们在这个函数的第二行处写的auto recp = receive.begin();会使得recp指向receive.end();
    			** 当然，此时receive.end() == receive.begin();
    			** 但是，当我们处理完这个else语句，也就是为某些节点更新了主链之后，
    			** 这些节点会把自己的主链传递给相邻节点，那么这些相邻节点就有了更新链 
    			** receive就不再为空。所以我们需要让recp重新指向receive的第一个数据。 
    			*/ 
    			recp = receive.begin(); 
    		}
    	}
    }
    
    int main(){
    	int n,m;
    	int u,v;
    	int k;
    	cin>>n>>m;
    	for(int i=0;i<m;i++){
    		cin>>u>>v;
    		adj[u].push_back(v);
    		adj[v].push_back(u);
    	}
    	cin>>t>>k;
    	string temp;
    	getline(cin,temp);
    	while(k--){
    		int nid,time,bid;  //节点编号，时刻，块编号 
    		vector<int> input = getInput();
    		if(input.size() == 3){
    			nid = input[0];
    			time = input[1];
    			bid = input[2];
    			create[time][nid].push_back(bid); 
    		}else{
    			nid = input[0];
    			time = input[1];
    			processUntil(time);
    			cout<<links[nid].size()+1<<" 0";
    			for(int i=0;i<links[nid].size();i++){
    				cout<<" "<<links[nid][i];
    			}
    			cout<<endl;
    		}
    	}
    	return 0;
    }

测试样例一的输入：

5 10
    1 2
    1 3 
    1 4
    1 5
    2 3
    2 4
    2 5
    3 4
    3 5
    4 5
    1 27
    1 1 1
    2 1 2
    3 1 3
    4 1 4
    5 1 5
    1 1      
    2 1      
    3 1      
    4 1
    5 1
    1 2
    2 2
    3 2
    4 2
    5 2
    1 10 10
    2 11 9
    1 11
    2 11
    3 11
    4 11
    5 11
    1 12
    2 12
    3 12
    4 12
    5 12

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTE1Njg2_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200228161755969.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTE1Njg2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTE1Njg2_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200228161956136.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTE1Njg2,size_16,color_FFFFFF,t_70
[80]: https://blog.csdn.net/qq_26873647/article/details/104273455