POJ - 2421 Constructing Roads（最小生成树，Prim模板题）

POJ - 2421 Constructing Roads

#include<cstdio>
const int N = 110, INF = 1e9;
int e[N][N],vis[N],dis[N];
int n,m,sum;
void prim()
{
    for(int i=1;i<=n;i++) {
    vis[i]=0;dis[i]=e[1][i];//从第一组开始 }dis[1]=0;vis[1]=1;for(int i=1;i<n;i++) //n个点，需要n-1条边 {
    int minn=INF,k; for(int j=1;j<=n;j++) if(vis[j]==0&&dis[j]<minn) {
    k=j;//记录你这个点 minn=dis[j];//记录最小值 }vis[k]=1;sum+=minn;for(int j=1;j<=n;j++) {
     if(vis[j]==0&&dis[j]>e[k][j]) //松弛 dis[j]=e[k][j];} }
}
int main()
{
    while(scanf("%d",&n)!=EOF){
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&e[i][j]);scanf("%d",&m);while(m--){
    int a,b;scanf("%d%d",&a,&b);e[a][b]=e[b][a]=0;} sum=0;prim();printf("%d\n",sum);}return 0;
}