本文共 1345 字，大约阅读时间需要 4 分钟。

Description

据新闻报道，Orz教主在太平洋中央建了一个大游乐园，其中有许多小岛，每个小岛上有且仅有一个游乐设施，有的小岛与小岛之间有海底隧道连接，而有的没有，一个游乐设施对一个人只开放一次，花的钱与得到的快乐值成正比。一开始，你可以选择被空投到任意一个小岛。当你想离开游乐园时，你可以打电话叫飞机来接，但不能再次被空投。

fhn非常有钱，他想在游乐园里得到最大的快乐值。 而czm则比较穷，他的愿望只是玩最多的游乐设施。

Input

第一行： n (代表有n个小岛)（n<=200）

以下n行，依次表示使用小岛1–小岛n上的游乐设施所花的钱 e (代表有e条海底隧道) 接着e行，每行2个数，表示这两个小岛之间有海底隧道连接

Output

第一行，czm最多可以游览的游乐园的个数。

第二行，fhn的游览方式所得的快乐值。

Sample Input

5

3 4 5 8 10 5 1 2 1 3 2 5 3 4 4 5

Sample Output

5

30

---

解题思路

一开始打的有向，wa了n次后，终于想起连通分量是无向图

找最大连通分量，分两个变量，一个记录设施数，一个记录快乐值

---

#include
   
    #include
    
     #include
     
      using namespace std;struct DT{   	int to,next;}e[50010];int head[300],n,num,Gun,v[300],t,s[300],m,sum,Max;queue
      
        f;//刚学queue的蒟蒻void BFS(int x){   	f.push(x);	v[x]=1,t=1,sum=s[x];	while(!f.empty()){   		for(int i=head[f.front()];i;i=e[i].next)		    if(!v[e[i].to]){   		    	sum+=s[e[i].to];//快乐值		    	v[e[i].to]=1;		    	++t;//设施数		    	f.push(e[i].to);		    }		f.pop();	}}int main(){   	scanf("%d",&n);	for(int i=1;i<=n;i++)	    scanf("%d",&s[i]);	scanf("%d",&m);	for(int i=1;i<=m;i++){   		int x,y;    	scanf("%d%d",&x,&y);		e[++num].to=y,e[num].next=head[x],head[x]=num;		e[++num].to=x,e[num].next=head[y],head[y]=num;	}    for(int i=1;i<=n;i++){   //不一定从1走是最优		if(!v[i]){   //用v记录遍历过没有			BFS(i);			Gun=max(Gun,t);//设施数			Max=max(Max,sum);//快乐值		}	}	printf("%d\n%d",Gun,Max);}
      
     
    
   

转载地址：http://hmnq.baihongyu.com/