HDU1233 还是畅通工程【最小生成树】

不念不忘少年蓝@ 2022-01-06 07:27 195阅读 0赞

## 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* ##

Hint Huge input, scanf is recommended.

### Prim算法： ###

#include<iostream>
    #include<cstdio>     //EOF,NULL
    #include<cstring>    //memset
    #include<cstdlib>    //rand,srand,system,itoa(int),atoi(char[]),atof(),malloc
    #include<cmath>           //ceil,floor,exp,log(e),log10(10),hypot(sqrt(x^2+y^2)),cbrt(sqrt(x^2+y^2+z^2))
    #include<algorithm>  //fill,reverse,next_permutation,__gcd,
    #include<string>
    #include<vector>
    #include<queue>
    #include<stack>
    #include<utility>
    #include<iterator>
    #include<iomanip>             //setw(set_min_width),setfill(char),setprecision(n),fixed,
    #include<functional>
    #include<map>
    #include<set>
    #include<limits.h>     //INT_MAX
    #include<bitset> // bitset<?> n
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> P;
    #define all(x) x.begin(),x.end()
    #define readc(x) scanf("%c",&x)
    #define read(x) scanf("%d",&x)
    #define read2(x,y) scanf("%d%d",&x,&y)
    #define read3(x,y,z) scanf("%d%d%d",&x,&y,&z)
    #define print(x) printf("%d\n",x)
    #define mst(a,b) memset(a,b,sizeof(a))
    #define disbit(x) x&-x
    #define lson(x) x<<1
    #define rson(x) x<<1|1
    #define pb push_back
    #define mp make_pair
    const int INF =0x3f3f3f3f;
    const int inf =0x3f3f3f3f;
    const int mod = 1e9+7;
    const int MAXN = 110;
    const int maxn = 10010;
    int n,m,v;
    int pos,imin ;
    int ans ;
    int st,ed;
    int vis[MAXN],dis[MAXN];
    int mapp[MAXN][MAXN];
    void Init(){
      mst(vis,0);
      ans = 0;
      for(int i = 1 ;i <= n; i++)  dis[i] = inf;
      for(int i = 1 ;i <= n; i++)
        for(int j = 1; j <= n; j++){
          if(i == j) mapp[i][j] = 0;
          else mapp[i][j] = inf;
        }
    }
    void prim(){
      for(int i = 1; i <= n ; i++)
          dis[i]  = mapp[1][i];
      dis[1] = 0;
      vis[1] = 1;
      for(int i = 1 ; i < n ; i ++) {
        pos = 1;
        imin  = inf;
        for(int j = 1 ; j <= n ; j++ )
            if(!vis[j]  && dis[j] < imin)  {
             pos = j , imin = dis[j];
            }
        vis[pos] = 1;
        ans += imin ;
        for(int j = 1; j <= n; j++)
           if(!vis[j] && mapp[pos][j] < dis[j])   dis[j] = mapp[pos][j];
        }
    }
    int main(){
      while(read(n) && n){
          m =  n * (n - 1) / 2;
          Init();
          for(int i = 0; i < m; i++){
              read3(st,ed,v);
              mapp[st][ed] = v;
              mapp[ed][st] = v;
          }
          prim();
          print(ans);
      }
      return 0;
    }

### Kruskal算法： ###

#include<iostream>
    #include<cstdio>     //EOF,NULL
    #include<cstring>    //memset
    #include<cstdlib>    //rand,srand,system,itoa(int),atoi(char[]),atof(),malloc
    #include<cmath>           //ceil,floor,exp,log(e),log10(10),hypot(sqrt(x^2+y^2)),cbrt(sqrt(x^2+y^2+z^2))
    #include<algorithm>  //fill,reverse,next_permutation,__gcd,
    #include<string>
    #include<vector>
    #include<queue>
    #include<stack>
    #include<utility>
    #include<iterator>
    #include<iomanip>             //setw(set_min_width),setfill(char),setprecision(n),fixed,
    #include<functional>
    #include<map>
    #include<set>
    #include<limits.h>     //INT_MAX
    #include<bitset> // bitset<?> n
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> P;
    #define all(x) x.begin(),x.end()
    #define readc(x) scanf("%c",&x)
    #define read(x) scanf("%d",&x)
    #define read2(x,y) scanf("%d%d",&x,&y)
    #define read3(x,y,z) scanf("%d%d%d",&x,&y,&z)
    #define print(x) printf("%d\n",x)
    #define mst(a,b) memset(a,b,sizeof(a))
    #define lowbit(x) x&-x
    #define lson(x) x<<1
    #define rson(x) x<<1|1
    #define pb push_back
    #define mp make_pair
    const int INF =0x3f3f3f3f;
    const int inf =0x3f3f3f3f;
    const int mod = 1e9+7;
    const int MAXN = 10005;
    const int maxn = 10010;
    struct node{
      int st,ed,v;
      bool operator < (node b) const{
         return v < b.v;
      }
    }rod[MAXN];
    int n,m,v;
    int cnt,ans;
    int pre[MAXN];
    
    int find(int x){ return x == pre[x] ? x : pre[x] = find(pre[x]);}
    bool join(int x,int y){
        if(find(x)!=find(y)){
          pre[find(y)] = find(x);
          return true;
        }
        return false;
    }
    void Init(){
      ans = 0;
      cnt = 0;
      for(int i = 0 ; i < MAXN ; i++){
        pre[i] = i;
      }
    }
    void kruskal(){
      for(int i = 0 ;i < cnt ; i++){
        int mp1 = find(rod[i].st);
        int mp2 = find(rod[i].ed);
        if(join(mp1,mp2)) ans+= rod[i].v;
      }
    }
    int main(){
      while(read(n) && n){
            Init();
            int a,b;
            for(int i = 0; i< n * (n - 1) / 2;i++){
              read3(a,b,v);
              rod[cnt].st = a;
              rod[cnt].ed = b;
              rod[cnt++].v = v;
            }
          sort(rod,rod+cnt);
          kruskal();
          print(ans);
      }
    
    }

转载于:https://www.cnblogs.com/llke/p/10780118.html