patA1034

首先DISS一下devc，个byd玩意一调试就闪退，感谢你帮鼠鼠治疗低血压，还是VS2019好用啊。

巨坑：N为通话数，按照极端情况，最多会有2N个人，所以要把数组开到2N个元素，否则会挂一个测试样例(段错误)。读题一定要认真。

分析题目，不难看出要用到DFS来找连通分量，然后计算每个连通分量的边权之和。计算边权之和有两种方法：(1)在DFS的过程中，对每个节点，先将与之相连的边的权值加上，然后再判断相邻节点是否已被访问过；每访问完一条边，就将其权值设为0。 (2)在edge结构体中增加一个属性，标记该边是否被访问过。
为了将字符串进行排序，可以使用stl的sort方法，也可以将数据存入std::map容器中，这样使用迭代器遍历的时候会自动将其按照增序排序。

实现方法1：

#include 
#include 
#include 
#include 
#include 
using namespace std;


/*储存一条边*/
struct edge{
	int v;	//节点编号，从0开始 
	int w;	//边权 
	edge(int x,int y):v(x),w(y){}
};

#define MAX 2000
//人数 
int N=0;	
//阈值 
int K=0;
//邻接表 
vector adj[MAX];
//姓名-编号map
map map1; 
//编号-姓名map
map map2;
//点权数组
int vw[MAX]={0}; 
//input中记录已经有多少节点
int mycount=0; 
//当前已知连通分量数
int compnum=0; 
//leader-节点数map 
map map3;
//找到的所有满足条件的连通分量
vector comp[MAX]; 
//标记节点是否被访问过
bool visit[MAX]={false}; 

using namespace std;

/*判断名字是否在map中，并返回编号。若名字不在map中，将名字加入map1和map2*/
int inmap(string name){
	map::iterator iter=map1.find(name);
	if(iter==map1.end()){
		map1.insert(pair(name,mycount));
		map2.insert(pair(mycount,name));
		return mycount++;
	}
	else{
		return (*iter).second;
	}
}

/*读取输入*/
void input(){
	cin>>N>>K;
	string name1,name2;
	int w;
	for(int i=0;i>name1>>name2>>w;
		int v1=inmap(name1);
		int v2=inmap(name2);
		/*将新边加入邻接表*/
		bool flag=true;
		for(int i=0;i vec=comp[j];
		//当前点权的最大值 
		int temp=0;
		//leader的编号 
		int leader;
		for(int i=0;itemp){
				temp=vw[u];
				leader=u;
			}
		}
		//将leader的信息加入map3
		string leadername=map2.find(leader)->second;
		map3.insert(pair(leadername,vec.size()));
	}
}



int main(void){
	input();
	find();
	getleader();
	
	//遍历map3，输出数据]
	cout<::iterator iter=map3.begin();iter!=map3.end();iter++) {
		cout<first<<" "<second<








实现方法2：
#include 
#include 
#include 
#include 
#include 
using namespace std;


/*储存一条边*/
struct edge{
	int v;	//节点编号，从0开始 
	int w;	//边权 
	bool isvisit;		//标记该边是否被visit过
	edge(int x,int y):v(x),w(y),isvisit(false){}
};

#define MAX 2000
//人数 
int N=0;	
//阈值 
int K=0;
//邻接表 
vector adj[MAX];
//姓名-编号map
map map1; 
//编号-姓名map
map map2;
//点权数组
int vw[MAX]={0}; 
//input中记录已经有多少节点
int mycount=0; 
//当前已知连通分量数
int compnum=0; 
//leader-节点数map 
map map3;
//找到的所有满足条件的连通分量
vector comp[MAX]; 
//标记节点是否被访问过
bool visit[MAX]={false}; 

using namespace std;

/*判断名字是否在map中，并返回编号。若名字不在map中，将名字加入map1和map2*/
int inmap(string name){
	map::iterator iter=map1.find(name);
	if(iter==map1.end()){
		map1.insert(pair(name,mycount));
		map2.insert(pair(mycount,name));
		return mycount++;
	}
	else{
		return (*iter).second;
	}
}

/*读取输入*/
void input(){
	cin>>N>>K;
	string name1,name2;
	int w;
	for(int i=0;i>name1>>name2>>w;
		int v1=inmap(name1);
		int v2=inmap(name2);
		/*将新边加入邻接表*/
		bool flag=true;
		for(int i=0;i vec=comp[j];
		//当前点权的最大值 
		int temp=0;
		//leader的编号 
		int leader;
		for(int i=0;itemp){
				temp=vw[u];
				leader=u;
			}
		}
		//将leader的信息加入map3
		string leadername=map2.find(leader)->second;
		map3.insert(pair(leadername,vec.size()));
	}
}



int main(void){
	input();
	find();
	getleader();
	
	//遍历map3，输出数据
	cout<::iterator iter=map3.begin();iter!=map3.end();iter++) {
		cout<first<<" "<second<

Pat


					
					
					
						相关
						
				
						
			
																
								
										SLF4J: Class path contains multiple SLF4J bindings
									
									
								 

        
								
							
							

																
								
										（八）自动化测试之selenium学习心得-Xpath选择器
									
									
								 

        
								
							
							

																
								
										SpringMVC中org.springframework.web.servlet.DispatcherServlet报红
									
									
								 

        
								
							
							

																
								
										sys.path.append("")作用
									
									
								 

        
								
							
							

																
								
										PAT乙级-1005 继续(3n+1)猜想
									
									
								 

        
								
							
							

																
								
										Linux 去掉PATH的重复路径
									
									
								 

        
								
							
							

																
								
										PAT乙级-1003 我要通过！
									
									
								 

        
								
							
							

																
								
										PAT乙级-1010 一元多项式求导
									
									
								 

        
								
							
							

																
								
										XPath JAVA用法总结及代码样例
									
									
								 

        
								
							
							

																
								
										使用jsonpath解析json内容
									
									
								 

        
								
							
							

																
								
										原型模式(Prototype Pattern)——对象的克隆
									
									
								 

        
								
							
							

																
								
										原型模式(Prototype Pattern)——对象的克隆