[ACM] poj 1258 Agri-Net (最小生成树）

Description

Input

Output

Sample Input

4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0

Sample Output

28

Source

#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
const int maxn=5010;
int parent[110];
int n;

struct Node
{
    int from,to,edge;
}node[maxn];

void init(int n)
{
    for(int i=1;i<=n;i++)
        parent[i]=i;
}

int find(int x)
{
    return parent[x]==x?x:find(parent[x]);
}

bool cmp(Node a,Node b)
{
    if(a.edge<b.edge)
        return true;
    return false;
}

int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        int m=1;
        int len;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            {
                scanf("%d",&len);
                if(i<j)
                {
                    int temp=m;
                    node[temp].from=i;
                    node[temp].to=j;
                    node[temp].edge=len;
                    m++;
                }
            }
        init(n);
        m=n*(n-1)/2;
        len=0;
        sort(node+1,node+1+m,cmp);
        for(int i=1;i<=m;i++)
        {
            int x=find(node[i].from);
            int y=find(node[i].to);
            if(x==y)
                continue;
            else
            {
                len+=node[i].edge;
                parent[x]=y;
            }
        }
        printf("%d\n",len);
    }
    return 0;
}

prim算法：

代码：

#include <stdio.h>
#include <iostream>
#include <string.h>
using namespace std;
const int maxn=110;
const int inf=0x7fffffff;
int map[maxn][maxn],low[maxn],visit[maxn];
//map数组用来记录地图。low数组用来保存与已增加树中的顶点相连的边，（保证权值最小的肯定在里边），visit用来记录该顶点是否已增加树中
int n;

int prim()
{
    int pos,Min,result=0;
    memset(visit,0,sizeof(visit));
    visit[1]=1,pos=1;//首先找的是1这个顶点。增加图中
    for(int i=1;i<=n;i++)
        if(i!=pos)
        low[i]=map[pos][i];//与1顶点相连的边地权值
    for(int i=1;i<n;i++)//每次增加一条边，n个顶点增加n-1条边，循环n-1次就能够了
    {
        Min=inf;
        for(int j=1;j<=n;j++)
            if(!visit[j]&&Min>low[j])
            {
                Min=low[j];//Min找到的是与已增加图中的顶点相连的边的最小值
                pos=j;//该顶点为j
            }
        result+=Min;//加上最小边
        visit[pos]=1;//新的顶点位置
        for(int j=1;j<=n;j++)
            if(!visit[j]&&low[j]>map[pos][j])
            low[j]=map[pos][j];//更新low[]值，新的与图中已有的点相连的边。假设比原来小的，就更新
    }
    return result;
}

int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            {
                scanf("%d",&map[i][j]);
                map[j][i]=map[i][j];
            }
        //对于题目中输入了map[i][i]的值的话，map数组不用预处理。假设没输入,那么memset(map,0x3f3f3f3f，sizeof(map))；最大化处理
        cout<<prim()<<endl;
    }
    return 0;
}