POJ 1251 + HDU 1301 Jungle Roads 【最小生成树】-白红宇

POJ 1251 + HDU 1301 Jungle Roads 【最小生成树】

阅读量：5909 次

发布时间：2019-06-19

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

题解

这是一道裸的最小生成树题，拿来练手，题目就不放了

个人理解 Prim有些类似最短路和贪心，不断找距当前点最小距离的点

Kruskal类似于并查集，不断找最小的边，如果不是一棵树的节点就合并为一颗树

AC代码：

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 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 = 30;const int maxn = 10010;int n,m,v;int pos,imin ;int ans ;char a,b ;int vis[MAXN],dis[MAXN];int mapp[MAXN][MAXN];void Init(){ mst(vis,0); ans = 0; for(int i = 0 ;i < n; i++) dis[i] = inf; for(int i = 0 ;i < n; i++) for(int j = 0; j < n; j++){ if(i == j) mapp[i][j] = 0; else mapp[i][j] = inf; }}void prim(){ for(int i = 0; i < n ; i++) dis[i] = mapp[0][i]; dis[0] = 0; vis[0] = 1; for(int i = 1 ; i < n ; i ++) { pos = 0; imin = inf; for(int j = 0 ; j < n ; j++ ) if(!vis[j] && dis[j] < imin) pos = j , imin = dis[j]; vis[pos] = 1; ans += imin ; for(int j = 0; j < n; j++) if(!vis[j] && mapp[pos][j] < dis[j]) dis[j] = mapp[pos][j]; }}int main(){ while(cin >> n && n){ Init(); for(int i = 1; i < n; i++){ cin >> a >> m ; int st = a -'A'; while(m--) { cin >> b >> v ; int ed = b - 'A'; 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 = 300;const int maxn = 10010;struct node{ int st,ed,v; bool operator < (node b) const{ return v < b.v; }}rod[MAXN];int n,m;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(cin >> n && n){ Init(); char a,b ; int m,v; for(int i = 1; i < n; i++){ cin >> a >> m ; int st = a -'A'; while(m--) { cin >> b >> v ; int ed = b - 'A'; rod[cnt].st = st; rod[cnt].ed = ed; rod[cnt++].v = v; } } sort(rod,rod+cnt); kruskal(); print(ans); } return 0;}