并查集最小生成树复习-白红宇

并查集最小生成树复习

阅读量：4483 次

发布时间：2019-06-08

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

HDU 1856 more is better 简单并查集

View Code

#include 
      
        int set[100010], num[100010]; int maxn = 1; int find( int x) {
    // return x == set[x] ? x : set[x] = find(set[x]);   if( x != set[x] )   {
    set[x] = find(set[x]);   } return set[x]; } void merge( int x, int y) {
    int x1 = find( x ); int y1 = find( y ); if( x1 != y1 )   {
    set[x1] = y1;     num[y1] += num[x1];     maxn = num[y1] > maxn ? num[y1] : maxn;   } } int main( ) {
    int N, a, b; while( scanf("%d",&N) != EOF )   {     maxn = 1; for( int i = 1; i <= 100000; i++)     {
    set[i] = i;          num[i] = 1;     } for( int i = 1; i <= N; i++)     {
             scanf("%d%d",&a, &b);          merge(a, b);     } // find( 1 ); // for( int i = 1; i <= 6; i++) //  printf("%d ", set[i]);     printf("%d\n",maxn);   } return 0; }

HDU 1162

1.Kruskal

View Code

#include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            using namespace std; int set[40000]; double xx[10000], yy[10000]; struct node {
    int i, j; double val; }T[100000]; void init( ) {
    for( int i = 1; i <= 20000; i++) set[i] = i; } int find( int x ) {
    return x == set[x] ? x : set[x] = find(set[x]); } void merge( int x, int y) {
    int x1 = find(x); int y1 = find(y); if( x1 != y1 ) set[x1] = y1; } bool cmp(node a, node b) {
    return a.val < b.val; } double kruskal(int cnt) {
      sort(T, T + cnt, cmp); int a, b; double c, ans = 0; for( int i = 0; i < cnt; i++)   {
        a = T[i].i;     b = T[i].j;     c = T[i].val; if( find(a) != find(b) )     {
            merge(a, b);         ans += c;     }   } return ans; } int main( ) {
    int N, cnt; while( scanf("%d",&N) != EOF )   {     cnt = 0;     init( ); for( int i = 1; i <= N; i++)     {
          scanf("%lf%lf",&xx[i], &yy[i]);     } for( int i = 1; i <= N; i++)     {
    for( int j = i + 1; j <= N; j++)       {
              T[cnt].i = i;           T[cnt].j = j;           T[cnt].val = sqrt((xx[i] - xx[j]) * (xx[i] - xx[j])  + ( yy[i] - yy[j]) * (yy[i] - yy[j]));           cnt++;       }     }     printf("%.2lf\n",kruskal(cnt));         } }

2.prim

View Code

#include 
      
        #include 
       
         #include 
        
          #include 
         
           double mp[200][200]; double dis[200]; int visit[200]; double xx[200],yy[200]; const int inf = 0x7f7f7f7f; void prim(int N) {
    for( int i = 1; i <= N; i++)    {
            dis[i] = mp[i][1];         visit[i] = 0;    } double sum = 0;    visit[1] = 1; for( int i = 1; i < N; i++)    {
    double t = inf; int k; for( int j = 1; j <= N; j++)       {
    if( !visit[j] && dis[j] < t )           {
                 t = dis[j];              k = j;           }       }       visit[k] = 1;       sum += t; for( int j = 1; j <= N; j++)       {
    if( !visit[j] && dis[j] > mp[k][j])          {
                dis[j] = mp[k][j];          }       }    }    printf("%.2lf\n",sum);  } int main( ) {
    int N, cnt; while( scanf("%d",&N) != EOF )   {
    for( int i = 1; i <= N; i++)     {
          scanf("%lf%lf",&xx[i], &yy[i]);     } for( int i = 1; i <= N; i++)     {
    for( int j = 1; j <= N; j++)       {
            mp[i][j] = ( i == j ) ? 0 : inf;         dis[i] = inf;       }     } for( int i = 1; i <= N; i++)     {
    for( int j = i + 1; j <= N; j++)       {
    double val = sqrt((xx[i] - xx[j]) * (xx[i] - xx[j])  + ( yy[i] - yy[j]) * (yy[i] - yy[j]));           mp[i][j] = val;           mp[j][i] = val;       }     }     prim(N);         } }

3.优先队列+ prim

View Code

#include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             struct node { double key; int v; bool operator < (node A) const { return key > A.key; } }; using namespace std; priority_queue
            
             q; int visit[300]; double xx[300], yy[300], mp[300][300], dis[300]; const int inf = 0x7f7f7f7f; void pri_prim(int N) { for( int i = 1; i <= N; i++) { dis[i] = mp[i][1]; node p; p.key = dis[i]; p.v = i; visit[i] = 0; q.push(p); } double sum = 0; while( !q.empty( )) { node p = q.top( ); q.pop(); int u = p.v; if ( visit[u] ) continue; visit[u] = 1; sum += p.key; for( int v = 1; v <= N; v++) { if( !visit[v] && dis[v] > mp[u][v] ) { dis[v] = mp[u][v]; node p; p.key = dis[v]; p.v = v; q.push(p); } } } printf("%.2lf\n", sum); } int main( ) { int N; while( scanf("%d",&N) != EOF ) { for( int i = 1; i <= N; i++) { scanf("%lf%lf",&xx[i], &yy[i]); } for( int i = 1; i <= N; i++) { for( int j = 1; j <= N; j++) { mp[i][j] = ( i == j ) ? 0 : inf; } } for( int i = 1; i <= N; i++) { for( int j = i + 1; j <= N; j++) { double val = sqrt((xx[i] - xx[j]) * (xx[i] - xx[j]) + ( yy[i] - yy[j]) * (yy[i] - yy[j])); mp[i][j] = val; mp[j][i] = val; } } pri_prim(N); } }