1 /* 学习了并查集 2 *先找出所有的不关联集合，找出其中最小的一个，然后先读最小的那本书 3 *图片不能显示，具体的计算方法是读的第一本书用全时，跟他关联的书用时间的一半 4 * 5 * 6 */ 7 #include <iostream> 8 #include <memory.h> 9 #include <algorithm> 10 using namespace std;
11 int B[
110];
//父节点 12 int V[
110];
//时间 13 int rank[
110];
//帙 14 int rd[
110][
110];
//关联的书 15 int n;
//书的种类 16 int set[
110][
110];
17 int len[
110];
//关联集合的长度，保存在祖先里 18 void make()
19 {
20 for(
int i=
0;i<n;i++)
21 {
22 B[i]=i;
23 }
24 }
25 int find(
int x)
26 {
27 if(B[x]!=x)
28 B[x]=find(B[x]);
29 return B[x];
30 }
31 void un(
int x,
int y)
32 {
33 x=find(x);
34 y=find(y);
35 if(x==y)
36 return;
37 if(rank[x]>rank[y])
38 {
39 B[y]=x;
40 }
41 else 42 {
43 if(rank[x]==rank[y])
44 rank[y]++;
45 B[x]=y;
46 }
47 }
48 int cmp(
const void* a,
const void* b)
49 {
50 return *(
int*)a>*(
int*)b;
51 }
52 int main()
53 {
54 int e;
55 cin>>n>>e;
56 while(n!=
0&&e!=
0)
57 {
58 memset(rd,
0,
sizeof(rd));
59 memset(V,
0,
sizeof(V));
60 memset(rank,
0,
sizeof(rank));
61 memset(len,
0,
sizeof(len));
62 memset(set,
0,
sizeof(set));
63 memset(B,
0,
sizeof(B));
64 for(
int i=
0;i<n;i++)
65 cin>>V[i];
66 while(e--)
67 {
68 int a,b;
69 cin>>a>>b;
70 rd[a][b]=
1;
71 }
72 make();
73 for(
int i=
0;i<n;i++)
74 for(
int j=
0;j<n;j++)
75 {
76 if(rd[i][j]==
1)
77 un(i,j);
78 }
79 int l=
0;
80 int ans=
0;
81 for(
int i=
0;i<n;i++)
82 {
83 int tem=find(i);
84 set[tem][len[tem]++]=V[i];
85 }
86 for(
int i=
0;i<n;i++)
87 {
88 if(len[i]!=
0)
89 {
90 qsort(set[i],len[i],
sizeof(set[i][
0]),cmp);
91 92 for(
int j=
0;j<len[i];j++)
93 {
94 if(j==
0)
95 ans+=set[i][j];
96 else 97 ans+=set[i][j]/
2;
98 }
99 }
100 }
101 cout<<ans<<endl;
102 cin>>n>>e;
103 }
104 }
105