修路问题（最小生成树-Prim）

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 using namespace std;
 5 
 6 #define M 100
 7 #define MAX 9999
 8 
 9 int map[M][M],visited[M],adjset[M];
10 int n,p,len;
11 
12 void ReadMap();
13 
14 void main()
15 {
16     int i,j,nlen,nid;
17     while (scanf("%d",&n)!=EOF)
18     {
19         //读取地图
20         ReadMap();
21         //初始化
22         memset(visited,0,sizeof(visited));
23         visited[0] = 1;
24         len = 0;
25         for (i=0;i<n;i++)    adjset[i] = map[i][0];
26         //Begin
27         for (i=1;i<n;i++)
28         {
29             //找到下一条符合条件的点
30             nlen = MAX;
31             for (j=0;j<n;j++)
32             {
33                 if (!visited[j] && adjset[j]<nlen)
34                 {
35                     nlen = adjset[j];
36                     nid = j;
37                 }
38             }
39             //访问找到的那个点
40             len += nlen;
41             visited[nid] = 1;
42             //更新邻接距离
43             for (j=0;j<n;j++)
44             {
45                 if (!visited[j] && map[j][nid]<adjset[j])
46                 {
47                     adjset[j] = map[j][nid];
48                 }
49             }
50         }
51         cout<<len<<endl;
52     }
53 }
54 
55 void ReadMap()
56 {
57     int i,j,a,b;
58     for (i=0;i<n;i++)
59     {
60         for (j=0;j<n;j++)
61         {
62             cin>>map[i][j];
63         }
64     }
65     cin>>p;
66     for (i=0;i<p;i++)
67     {
68         cin>>a>>b;
69         map[a-1][b-1] = map[b-1][a-1] = 0;
70     }
71 }