点这里
题意： 一共有n个村庄，给出每两个村庄间需要修的路的长度。以及给出q条已经修好的路，求最少还要修多少长度的路能使所有村庄连通。 题解： prim算法的板子题，详见点这里。
#include<bits/stdc++.h>
using namespace std
;
const int N
= 110;
const int inf
= 0x3f3f3f3f;
int n
, q
, a
, b
, ans
;
int d
[N
], vis
[N
];
int G
[N
][N
];
int prim(){
for(int i
= 1; i
<= n
; i
++) vis
[i
] = 0, d
[i
] = inf
;
ans
= d
[1] = 0;
for(int i
= 1; i
<= n
; i
++){
int x
= 0;
for(int j
= 1; j
<= n
; j
++)
if(!vis
[j
] && (!x
|| d
[j
] < d
[x
]))
x
= j
;
vis
[x
] = 1;
for(int y
= 1; y
<= n
; y
++)
if(!vis
[y
])
d
[y
] = min(d
[y
], G
[x
][y
]);
}
for(int i
= 2; i
<= n
; i
++) ans
+= d
[i
];
return ans
;
}
int main(){
while(~scanf("%d", &n
) && n
){
for(int i
= 1; i
<= n
; i
++)
for(int j
= 1; j
<= n
; j
++)
scanf("%d", G
[i
] + j
);
scanf("%d", &q
);
while(q
--){
scanf("%d%d", &a
, &b
);
G
[a
][b
] = G
[b
][a
] = 0;
}
printf("%d\n", prim());
}
return 0;
}
