学步园

HDU 1856 more is better 简单并查集

#include <stdio.h>

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 1162Eddy's picture

1.Kruskal

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
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

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

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

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <queue>
#include <map>
#include <math.h>

struct node
{
double key;
int v;
bool operator < (node A) const
  { 
return key > A.key;
  }
};

using namespace std;
priority_queue<node>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);      
  }
}