HOJ 1102 Constructing Roads（最小生成树，水题）

最小生成树，水题
题目意思：
有n个村庄，每两个村庄都有一段距离。现在已经修好了e条路，
问，最少再修多少路程（修的路的所有的总里程）， 使得全部连通。
本题要点：
1、首先，把修好的路的距离，全部改为0， 再套用 kruskal 算法， 求到最小生成树，就是要修的总里程。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MaxN = 110, INF = 0x3f3f3f3f;
int a[MaxN][MaxN], d[MaxN];
int n, m, e;
bool vis[MaxN];void prim()
{
    memset(vis, false, sizeof vis);memset(d, 0x3f, sizeof d);d[1] = 0;for(int i = 1; i < n; ++i){
    int x = -1;for(int j = 1; j <= n; ++j){
    if(!vis[j] && (-1 == 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], a[x][y]);}}
}int main()
{
    int x, y;while(scanf("%d", &n) != EOF){
    for(int i = 1; i <= n; ++i){
    for(int j = 1; j <= n; ++j){
    scanf("%d", &a[i][j]);	}}scanf("%d", &e);for(int i = 0; i < e; ++i){
    scanf("%d%d", &x, &y);a[x][y] = a[y][x] = 0;}prim();int ans = 0;for(int i = 2; i <= n; ++i){
    ans += d[i];}printf("%d\n", ans);}return 0;
}/* 3 0 990 692 990 0 179 692 179 0 1 1 2 *//* 179 */