记录编号	58108	评测结果	AAAAAAAAAA
题目名称	读书	最终得分	100
用户昵称	digital-T	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2013-04-17 15:22:23	内存使用	0.31 MiB

#include<fstream>
#include<algorithm>
#include<vector>
#include<cstdio>
using namespace std;
ifstream fi("reading.in");
ofstream fo("reading.out");
int n,m;
int Length,refer[101],sum,tmpsum,mini;
class set//并查集的集合C
{
public:
	int count,parent,tim;
}C[101];
void makeset(int x)//集
{
	C[x].count=1;
	C[x].parent=-1;
}
int findformerge(int x)//查
{
	int y=x,z=x,tmp;
	while(C[z].parent!=-1)z=C[z].parent;
	while(C[y].parent!=-1)tmp=y,y=C[y].parent,C[tmp].parent=z;//路径压缩
	return z;
}
void merge(int x,int y)//并
{
	int e=findformerge(x),f=findformerge(y);
	if(e==f)return;
	if(C[e].count>C[f].count)
	{
		C[f].parent=x;
	}
	else 
	{
		if(C[e].count==C[f].count)
			C[f].count++;
		C[e].parent=y;
	}
}
int findset(int x)//查
{
	int z=x;
	while(C[z].parent!=-1)z=C[z].parent;
	return z;
}
int main()
{
	fi>>n>>m;//n本书编号为0~n-1
	int i,j,k,l;
	while(n!=0||m!=0)
	{
		vector <int> p[101];
		Length=0;sum=0;
		bool boo[101]={false};
		//====================================================================
		for(i=0;i<n;i++)
		{
			fi>>C[i].tim;
			makeset(i);
		}
		for(i=1;i<=m;i++)
		{
			fi>>k>>l;
			merge(k,l);
		}
		//====================================================================
		for(i=0;i<n;i++)//打造出所有根节点
		if(findset(i)==i)
		{
			//fo<<i<<endl;
			boo[i]=true;
			Length++;
			p[Length].push_back(i);
			refer[Length]=i;
		}
		for(i=0;i<n;i++)//将非根节点插入树中
		if(!boo[i])
		{
			k=findset(i);
			//fo<<i<<' '<<k<<endl;
			for(j=1;j<=Length;j++)
			if(k==refer[j])
			{
				//fo<<i<<' '<<j<<' '<<refer[j]<<endl;
				p[j].push_back(i);
				break;
			}
		}
		//====================================================================
		for(i=1;i<=Length;i++)
		{
			mini=100001;tmpsum=0;	//fo<<"SIZE"<<p[i].size()<<endl;
			for(j=0;j<p[i].size();j++)
			{
				if(C[p[i][j]].tim<mini)mini=C[p[i][j]].tim;
				tmpsum+=C[p[i][j]].tim/2;
				//fo<<i<<' '<<j<<' '<<p[i][j]<<' '<<C[p[i][j]].tim<<endl;
			}
			if(mini%2==0)tmpsum+=mini/2;
			else tmpsum+=mini/2+1;
			sum+=tmpsum;
		}
		//for(i=0;i<n;i++)fo<<findset(i)<<endl;fo<<Length<<endl;
		fo<<sum<<endl;
		//=====================================================================
		fi>>n>>m;
	}
	return 0;
}