G - 还是畅通工程

        题目意思是找使公路路径最小。也就是最小生成树。但是这里应该有多种解法,我看了两种解法,一种是Prim最小生成树算法,一种是使用类似并查集思想的Kruskal算法。个人感觉Kruskal算法比prim算法好理解一些,但是Kruskal算法的效率要比Prim低。


题目:飞机票直达(G - 还是畅通工程


下面公布两份代码:


prim算法代码:

Memory: 1772 KB
Time: 218 MS
Language: C++
Result: Accepted
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <memory.h>
using namespace std;

const int INF=0x3f3f3f3f;
const int maxm=100+1;

int n, num, i, j;
int node[maxm][maxm], dis[maxm], flag[maxm];

void Init()
{
    int x, y, val;
    num=n*(n-1)/2;
    memset(flag, 0, sizeof(flag));      //初始化每个点都不在集合中
    memset(node, INF, sizeof(node));    //初始化各个距离为无穷大
    memset(dis, -1, sizeof(dis));       //初始化为-1意思为当前点到集合没有距离
    for(i=0;i<num;i++)
    {
        scanf("%d%d%d", &x,&y,&val);  //获得边权值
        node[x][y]=node[y][x]=val;
    }
}

int Prim()
{
    int sum=0;
    dis[1]=0;
    flag[1]=1;
    for(i=2;i<=n;i++)       //初始化其他各点到起点集合的位置
        dis[i]=node[1][i];
    for(i=1;i<n;i++)
    {
        int tmin=999999, cur=-1;
        for(j=2;j<=n;j++)
        {
            if(!flag[j]&&(dis[j]<tmin))    //找距离当前集合最小的权
                {
                    tmin=dis[j];
                    cur=j;
                }
        }
        flag[cur]=1;    //将这个权加入集合中
        sum+=dis[cur];
        for(j=2;j<=n;j++)       //更新各个点到集合的距离
        {
            if(!flag[j]&&node[cur][j]<dis[j])
                dis[j]=node[cur][j];
        }
    }
    return sum;
}

int main()
{
    while(scanf("%d", &n)!=EOF && n)
    {
        Init();
        int ans=Prim();
        printf("%d\n", ans);
    }
    return 0;
}

Kruskal算法算法代码:

Memory: 1800 KB
Time: 249 MS
Language: C++
Result: Accepted
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

const int maxn=10000;
const int maxm=100;
struct Node
{
    int u, v, val;
}node[maxn];

int n, num, i, j;
int parent[maxm];

void Init()
{
    num=n*(n-1)/2;
    for(i=0;i<num;i++)
        scanf("%d%d%d", &node[i].u, &node[i].v, &node[i].val);  //获得边权值
    for(i=1;i<=n;i++)
        parent[i]=i;        //初始化父节点为自己
}

bool cmp(Node a, Node b)
{
    return a.val<b.val;     //权值排序,从小到大
}

int Find(int x)
{
    return x==parent[x]?x:parent[x]=Find(parent[x]);    //找父节点并且使用路径压缩
}

int Kruskal()
{
    int sum=0;
    for(i=0;i<num;i++)
    {
        int fa=Find(node[i].u);
        int fb=Find(node[i].v);
        if(fa!=fb)      //不在同一个集合就结合
        {
            sum+=node[i].val;
            parent[fa]=fb;
        }
    }
    return sum;
}

int main()
{
    while(scanf("%d", &n)!=EOF && n)
    {
        Init();
        sort(node, node+num, cmp);
        int ans=Kruskal();
        printf("%d\n", ans);
    }
    return 0;
}