ZOJ

ZOJ - 1586 QS Network （Prim）
 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 const int maxn = 1000+10;
 5 const int MAX = 100000;//无穷远 
 6 int n;
 7 int cost[maxn];
 8 int Edge[maxn][maxn];
 9 int lowcost[maxn];
10 void Init()
11 {
12     cin>>n;
13     for(int i=0;i<n;i++)
14     {//读入每个结点的适配器价值 
15         cin>>cost[i];
16     }
17     for(int i=0;i<n;i++)
18     {//建立邻接矩阵 
19         for(int j=0;j<n;j++)
20         {
21             cin>> Edge[i][j];
22             if(i == j) Edge[i][j] = MAX; 
23             else Edge[i][j] += cost[i]+cost[j]; 
24         }
25     }
26     memset(lowcost,0,sizeof(lowcost));
27 }
28 
29 void prim()
30 {
31     int sum = 0;
32     //从源点0开始
33     lowcost[0] = -1;//-1表示当前结点已经加入
34     for(int i=1;i<n;i++)
35         lowcost[i] = Edge[0][i];
36     for(int i=1;i<n;i++)
37     {//把其他 n-1 个结点 扩展到生成树中 
38         int min = MAX,pos;
39         for(int j=0;j<n;j++)//找到权值最小的边 
40         {
41             if(lowcost[j] != -1 && lowcost[j]<min)
42             {
43                 min = lowcost[j];pos = j;
44             }
45         }
46         //将新顶点加入
47         lowcost[pos] = -1;
48         sum += min;
49         //更新lowcost数组
50          for(int k=0;k<n;k++)
51          {
52              if(lowcost[k] > Edge[pos][k]) 
53              lowcost[k] = Edge[pos][k];
54          }
55      } 
56      cout<<sum<<endl; 
57 }
58 
59 int main()
60 {
61     int t;
62     cin>>t;
63     while(t--)
64     {
65         Init();
66         prim();
67     }
68     return 0;
69 }