HDU1233 还是畅通工程【最小生成树】-白红宇

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

阅读量：6123 次

发布时间：2019-06-21

本文共 4210 字，大约阅读时间需要 14 分钟。

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
     
      #include
      
            //EOF,NULL#include
       
            //memset#include
        
             //rand,srand,system,itoa(int),atoi(char[]),atof(),malloc#include
         
                     //ceil,floor,exp,log(e),log10(10),hypot(sqrt(x^2+y^2)),cbrt(sqrt(x^2+y^2+z^2))#include
          
            //fill,reverse,next_permutation,__gcd,#include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                   //setw(set_min_width),setfill(char),setprecision(n),fixed,#include
                  
                   #include
                   #include
                    
                     #include
                     
                       //INT_MAX#include
                      
                        // bitset
                        nusing namespace std;typedef long long ll;typedef pair
                       
                         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_pairconst 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
     
      #include
      
            //EOF,NULL#include
       
            //memset#include
        
             //rand,srand,system,itoa(int),atoi(char[]),atof(),malloc#include
         
                     //ceil,floor,exp,log(e),log10(10),hypot(sqrt(x^2+y^2)),cbrt(sqrt(x^2+y^2+z^2))#include
          
            //fill,reverse,next_permutation,__gcd,#include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                   //setw(set_min_width),setfill(char),setprecision(n),fixed,#include
                  
                   #include
                   #include
                    
                     #include
                     
                       //INT_MAX#include
                      
                        // bitset
                        nusing namespace std;typedef long long ll;typedef pair
                       
                         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_pairconst 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

你可能感兴趣的文章