hdu 1102 Constructing Roads

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define maxn 1001
 5 using namespace std;
 6 const int inf=1<<30;
 7 
 8 int g[maxn][maxn];
 9 int dis[maxn*6];
10 bool vis[maxn*6];
11 int sum,n;
12 
13 void prim()
14 {
15     sum=0;
16     memset(vis,false,sizeof(vis));
17     for(int i=1; i<=n; i++) dis[i]=g[1][i];
18     dis[1]=0;
19     for(int i=1; i<=n; i++)
20     {
21         int x,m=inf;
22         for(int y=1; y<=n; y++) if(!vis[y]&&dis[y]<m) m=dis[x=y];
23         vis[x]=true;
24         sum+=m;
25         for(int y=1; y<=n; y++) if(!vis[y]) dis[y]=min(dis[y],g[x][y]);
26     }
27 }
28 
29 int main()
30 {
31     while(scanf("%d",&n)!=EOF)
32     {
33         for(int i=1; i<=n; i++)
34         {
35             for(int j=1; j<=n; j++)
36             {
37                 scanf("%d",&g[i][j]);
38             }
39         }
40         int q;
41         scanf("%d",&q);
42         int a,b;
43         for(int i=0; i<q; i++)
44         {
45             scanf("%d%d",&a,&b);
46             g[a][b]=g[b][a]=0;
47         }
48         sum=0;
49         prim();
50         printf("%d\n",sum);
51     }
52     return 0;
53 }