hdu 1102 Constructing Roads

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1102

题目分类：prim求MST（最小生成树）

代码：

#include<bits/stdc++.h>

using namespace std;

const int N=1000;
const int inf=0x3f3f3f3f;
int vis[N],lowc[N];
int cost[N][N];
int n;

int prim(int n,int st)
{
    int minc,res=0,i,j,pos;
    memset(vis,0,sizeof(vis));
    vis[st]=1;
    for(i=0;i<n;i++)
        lowc[i]=cost[st][i];
    lowc[st]=inf;

    for(i=0;i<n;i++)
    {
        minc=inf;
        for(i=0;i<n;i++)
        {
            minc=inf;
            for(j=0;j<n;j++)
            {
                if(vis[j]==0&&minc>lowc[j])
                {
                    minc=lowc[j];
                    pos=j;
                }
            }

        }
        if(inf==minc) return -1;
        res+=minc;
        vis[pos]=1;
        for(j=0;j<n;j++)
        {
            if(vis[j]==0&&lowc[j]>cost[pos][j])
                lowc[j]=cost[pos][j];
        }
    }
    return res;
}

int main()
{
    int a,b,m;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            scanf("%d",&cost[i][j]);
        }
    }

    scanf("%d",&m);
    while(m--)
    {
        scanf("%d %d",&a,&b);
        cost[a-1][b-1]=0;
        cost[b-1][a-1]=0;
    }
    int ans=prim(n,n-1);
    printf("%d
",ans);
    return 0;
}

#include<bits/stdc++.h>

using namespace std;
const int V=200;
#define INF 0x3f3f3f3f

int cost[V][V];
int mincost[V];
bool used[V];
int v;

int prim()
{
    for(int i=0;i<v;i++)
    {
        mincost[i]=INF;
        used[i]=0;
    }
    mincost[0]=0;
    int res=0;

    while(1)
    {
        int vv=-1;
        for(int u=0;u<v;u++)
        {
            if(!used[u]&&(vv==-1||mincost[u]<mincost[vv]))
                vv=u;
        }

        if(vv==-1) break;
        used[vv]=1;
        res+=mincost[vv];
        for(int u=0;u<v;u++)
            mincost[u]=min(mincost[u],cost[vv][u]);
    }
    return res;
}

int main()
{
    int a,b,m,n;
    while(scanf("%d",&v)!=EOF)
    {
        for(int i=0;i<v;i++)
        {
            for(int j=0;j<v;j++)
            {
                scanf("%d",&cost[i][j]);
            }
        }
        scanf("%d",&m);
        while(m--)
        {
            scanf("%d %d",&a,&b);
            cost[a-1][b-1]=0;
            cost[b-1][a-1]=0;
        }
        int ans=prim();
        printf("%d
",ans);
    }

    return 0;
}