POJ2421 Constructing Roads(最小生成树)

题意：

村庄之间连通，要求输出最小权值和，注意有些村庄已经连通

要点：

Prim算法稍微变一下，因为是求权值和，已经连通的之间权值改为0即可，反正为0后面算的时候肯定是最小值，会加入集合的，然后权值又是0不影响。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int map[105][105], low[105];
bool vis[105];
int n, m;int prim()
{int i, j,mark,min,sum=0;memset(vis, false, sizeof(vis));for (i = 1; i <= n; i++)low[i] = map[1][i];vis[1] = true;for (i = 2; i <= n; i++){min = 0xfffff;for (j = 1; j <= n;j++)if (!vis[j] && min > low[j]){min = low[j];mark = j;}vis[mark] = true;sum += min;for (j = 1; j <= n; j++)if (!vis[j] && map[mark][j] < low[j])low[j] = map[mark][j];}return sum;
}
int main()
{int i, j,x,y;while (~scanf("%d", &n)){for (i = 1; i <= n; i++)for (j = 1; j <= n; j++)scanf("%d", &map[i][j]);scanf("%d", &m);while (m--){scanf("%d%d", &x, &y);map[x][y] = 0;		//这两个已经通了，那么直接赋值为0，加起来不影响结果map[y][x] = 0;}printf("%d\n", prim());}return 0;
}