HDU-1233-还是畅通工程(最小生成树)

Problem Description
某省调查乡村交通状况,得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可),并要求铺设的公路总长度为最小。请计算最小的公路总长度。
 
Input
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 );随后的N(N-1)/2行对应村庄间的距离,每行给出一对正整数,分别是两个村庄的编号,以及此两村庄间的距离。为简单起见,村庄从1到N编号。
当N为0时,输入结束,该用例不被处理。
 
Output
对每个测试用例,在1行里输出最小的公路总长度。
 
Sample Input
3
1 2 1
1 3 2
2 3 4
4
1 2 1
1 3 4
1 4 1
2 3 3
2 4 2
3 4 5
0
 
Sample Output
3
5
 
Hint
Huge input, scanf is recommended.

思路:最小生成树模板题。两种算法都可以,直接上代码。

坑点:(C++过,G++超时//暂时不知道为啥)


克鲁斯卡尔算法解:

#include<cstdio>
#include<algorithm>
using namespace std;
int bin[205],n;
int flag[205];
struct node{
    int x,y,val; 
}a[10005];

int cmp(node x,node y){
    if(x.val!=y.val) return x.val<y.val;
}

int find(int x) {
    if(bin[x] == x)
        return bin[x];
    return bin[x] = find(bin[x]);
}
void merge(int x,int y){
    int fx=find(x);
    int fy=find(y);
    if(fx!=fy)
    bin[fx]=fy;
}
int same(int x,int y){
    if(find(x)==find(y))  return 1;
    return 0;
}

int main(){
    while(scanf("%d",&n)&&n){
        int i;
        int m=n*(n-1)/2;
        for(i=1;i<=n;i++){
            bin[i]=i;
            flag[i]=0;
        }
        for(i=0;i<m;i++)
            scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].val);
        sort(a,a+m,cmp);
         int sum=0,cnt=0;
        for(i=0;i<m;i++){
            if(cnt==n-1) break;        
            if(same(a[i].x,a[i].y))continue;

            sum+=a[i].val;
            merge(a[i].x,a[i].y);
            cnt++;
        }
        printf("%d
",sum);
    }
    return 0;
}

Prim算法解:

#include<cstdio>
#include<algorithm>
using namespace std;

struct node{
   int x,y,val;
}a[5005];

int cmp(node x,node y){
    if(x.val!=y.val) return x.val<y.val;
}

int main(){
    int i,sum,n,m,num;
    int flag[200];//标记数组表示,目前节点在集合当中。 
    while(scanf("%d",&n),n)
    {
       m=(n*(n-1))/2;
       for(i=0;i<m;i++)
       {
          scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].val);
       }
       sort(a,a+m,cmp);//按照len排序 
       for(i=1;i<=n;i++) flag[i]=0;//初始化标记 
       flag[a[0].x]=1;//标记第一个节点 
       sum=0;
       for(i=0;i<m;i++)
       {
          num=flag[a[i].x]+flag[a[i].y];
           if(num==1)//如果两个都没标记肯定不在这个集合里,所以不操作,如果两个都标记了说明两个都在集合里了,则不用修路了 
           {
             sum+=a[i].val;
             flag[a[i].x]=flag[a[i].y]=1;
             i=0;//可能有漏掉的值小的路需要从头开始找 (当num==0时就会被漏掉) 
          }
       }
       printf("%d
",sum);
    }
    return 0;
}
原文地址:https://www.cnblogs.com/yzhhh/p/9943593.html