poj1287解题报告

对于学过图和Prim算法的人来说，此题是一道不折不扣的水题，尤其是输入范围限定在了50之内，所以即便我用了O（n^3）的算法也只用了16MS就AC了。

前期建图，我用的是邻接矩阵，当两个节点有多个路径时选择最小的录入。

建完图后开始对图操作，使用的是Prim算法，其精髓是选取与集合A相接的最小边，其中集合A代表已选择节点。有疑问的可以百度Prim或参考算法导论的相关章节

具体代码如下，Memory 180K  Time  16MS

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

const int maxn=50+10;
int G[maxn][maxn];
bool vis[maxn];
int p,r;

struct Node
{
    int p[maxn];
    int length;
}v;

void init(struct Node &s)
{
    s.length=1;
}

int main()
{
    while(scanf("%d",&p) && p)
    {
        int x,y,d;
        scanf("%d",&r);
        if(r==0) { printf("0\n"); continue; }
        memset(G,0,sizeof(G));   //一定不要忘了初始化
        memset(vis,false,sizeof(vis));
        init(v);
        for(int i=0;i<r;i++)
        {
            scanf("%d%d%d",&x,&y,&d);
            if(!G[x][y]) {G[x][y]=d; G[y][x]=d;}
            else { int k=min(G[x][y],d); G[x][y]=k; G[y][x]=k; }
        }    //建图
        v.p[v.length++]=1;
        vis[1]=true;
        int minn,ans=0,mark;
        while(v.length<=p)
        {
            minn=10000; mark=0;
            for(int i=1;i<v.length;i++)
            {
                int k=v.p[i];
                for(int j=1;j<=p;j++)
                {
                    if(vis[j]) continue;
                    if(!G[j][k]) continue;
                    if(minn>G[k][j])
                    {
                        mark=j;
                        minn=G[k][j];
                    }
                }
            }
            ans+=minn;
            vis[mark]=true;
            v.p[v.length++]=mark;
        }
        printf("%d\n",ans);
    }
    return 0;
}

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

const int maxn=50+10;
int G[maxn][maxn];
bool vis[maxn];

int p,r;

int main()
{
    while(scanf("%d",&p) && p)
    {
        int x,y,d;
        scanf("%d",&r);
        if(r==0) { printf("0\n"); continue; }
        memset(G,0,sizeof(G));   //一定不要忘了初始化
        memset(vis,false,sizeof(vis));
        for(int i=0;i<r;i++)
        {
            scanf("%d%d%d",&x,&y,&d);
            if(!G[x][y]) {G[x][y]=d; G[y][x]=d;}
            else { int k=min(G[x][y],d); G[x][y]=k; G[y][x]=k; }
        }    //建图
        int minn,ans=0,mark;
        for(int i=1;i<=p;i++)
        {
            minn=10000;
            mark=0;
            if(vis[i]) continue;
            for(int j=1;j<=p;j++)
            {
                if(!G[j][i]) continue;
                if(minn>G[j][i])
                {
                    mark=j;
                    minn=G[j][i];
                }
            }
            ans+=minn;
            vis[mark]=true;
        }
        printf("%d\n",ans);
    }
    return 0;
}