3366 矿石

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 钻石 Diamond

题目描述 Description

经历了千辛万苦，小J找到了N块矿石。这些矿石都有毒性，但只要将两块矿石放在一起，再分开即可解毒。但任一两块矿石都可以互相吸引。为了降低吸引力，小J将他们放入一个直径仅能容下一块矿石，且足够高的木桶中并借此完成消毒。

小J一次可以：

将任意一块未消毒矿石放入桶中。

2. 取出桶顶的一块矿石消毒，花费的体力值为桶顶和桶中第二个矿石之间的吸引力。若不是所有矿石都消过毒或都未消过毒，则桶不能为空。

小J想知道最少花费多少体力才可以获得所有矿石。

输入描述 Input Description

第一行,n

第二行，每行n个数，第i块矿石与第j块矿石的吸引力Cij

输出描述 Output Description

一行,最小体力花费

样例输入 Sample Input

0 4 2

4 0 3

2 3 0

样例输出 Sample Output

数据范围及提示 Data Size & Hint

对于30%的数据，N<=15

对于100%的数据，N<=500

重在对题目的理解，求最小生成树，注意数据范围

 1 #include<cstdio>
 2 #include<algorithm>
 3 
 4 using namespace std;
 5 struct Edge{
 6     int x,y,w;
 7     bool operator < (const Edge &a) const 
 8     {
 9         return w < a.w;
10     }
11 }e[250100];
12 int fa[510];
13 int ans,cnt,n,p;
14 
15 void add(int u,int v,int w)
16 {
17     ++cnt;
18     e[cnt].x = u;
19     e[cnt].y = v;
20     e[cnt].w = w;
21 }
22 int find(int x)
23 {
24     return x==fa[x]?x:fa[x]=find(fa[x]);
25 }
26 int main()
27 {
28     scanf("%d",&n);
29     for (int i=1; i<=n; ++i)
30         for (int a,j=1; j<=n; ++j)
31         {
32             scanf("%d",&a);
33             if (i!=j) add(i,j,a);
34         }
35     sort(e+1,e+cnt+1);
36     for (int i=1; i<=n; ++i) fa[i] = i;
37     for (int i=1; i<=cnt; ++i)
38     {
39         int rx = find(e[i].x);
40         int ry = find(e[i].y);
41         if (rx!=ry)
42         {
43             fa[rx] = ry;
44             ans += e[i].w;
45             ++p;
46             if (p==n-1) break ;
47         }
48     }
49     printf("%d",ans);
50     return 0;
51 }