[最小生成樹]USACO Dec07 Silver: Building Roads 建造路徑 roads 解題報告

【題目描述】
譯 by CmYkRgB123

Farmer John 剛剛得到了幾個新農場！他想把這幾個農場用路連接起來，這樣他就可以通過筆直的公路從一個農場到另一個農場了。現在已經有了幾條連接着的農場。

N (1 ≤ N ≤ 1,000) 個農場中，每個農場的位置在座標平面的 (Xi, Yi) (0 ≤ Xi ≤ 1,000,000; 0 ≤ Yi ≤ 1,000,000)。已經有 M (1 ≤ M ≤ 1,000) 條路以前就被建好了。請你幫助 Farmer John 考慮建設儘量少長度的額外的路，使他的農場連在一起。

輸入

* 第 1 行: 兩個整數: N , M

* 第 2..N+1 行: 兩個整數 Xi , Yi

* 第 N+2..N+M+2 行: 兩個整數: i , j, 表示已經存在從農場i到農場j的路。

輸出

* 第 1 行: 額外的路的最少長度，保留2小數。 請使用 64 位的浮點數。

樣例輸入

4 1

1 1

3 1

2 3

4 3

1 4

樣例輸出

4.00

【分析】

圖論，最小生成樹問題。這是個包含M條邊的最小生成樹問題。

可以參見BYVoid大犇的解題報告：

http://www.byvoid.com/blog/usaco-dec07-silver-building-roads/

以下題解來自BYVoid：

求包含給定的M條邊的最小生成樹。

可以用Kruskal算法加並查集，再讀入M條邊的時候先把這些邊加入樹中，再把最小的不構成環的N(N-1)/2-1-M條邊加入樹，算出邊權和。

【我的代碼】

用了樹狀並查集+路徑壓縮+Kruskal算法，不過還是很慢，10組數據總耗時將近3秒！ 我在我的代碼下面給出了BYVoid大犇的代碼，速度巨快！

我的代碼：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
int N,M;
double ans=0;
bool used[1001][1001];
int B=0;
int X[1001];
int Y[1001];

class Road
{
public:
    int s,e;
    double len;
}R[1000001];

struct Node
{
    int parent; //父节点编号
    int count; //集合中元素的个数
}UnionFindSet[1000001];   
   
int top=0;
   
void InitUFS(int n)
{
    for(int i=1; i<=N;++i)
    {
        UnionFindSet[i].count = 1;
        UnionFindSet[i].parent = i;
    }
}

int Find(int x)
{
    int i = x;
    while(i != UnionFindSet[i].parent)
        i = UnionFindSet[i].parent;

    int j = x;
    while(j != i)
    {
        int tmp = UnionFindSet[j].parent;
        UnionFindSet[j].parent = i;
        j = tmp;
    }
    return i;
}

void Union(int x, int y)
{
      x = Find(x);
      y = Find(y);
      if(y == x) return;
      if(UnionFindSet[x].count > UnionFindSet[y].count)
      {
            UnionFindSet[y].parent = x;
            UnionFindSet[x].count += UnionFindSet[y].count;
      }
      else
      {
            UnionFindSet[x].parent = y;
            UnionFindSet[y].count += UnionFindSet[x].count;
      }
}

double GetDist(int x,int y)
{
    double tmp1,tmp2;
    tmp1=X[x]-X[y];
    tmp2=Y[x]-Y[y];
    double tmp=tmp1*tmp1+tmp2*tmp2;
    return sqrt(tmp);
}

int cmp(const void *a,const void *b)
{
    class Road *c=(class Road *)a;
    class Road *d=(class Road *)b;
    if(c->len<d->len)
        return -1;
    return 1;
}

void Kruskal()
{
    B=0;
    int NC=N*(N-1)/2;
    int t=1;
    int ts,te;
    while(B<NC-1-M &&t<=NC)
    {
        ts=R[t].s;
        te=R[t].e;
        if(Find(ts)!=Find(te))
        {
            ans+=R[t].len;
            Union(ts,te);
            B++;
        }
        t++;
    }
    printf("%.2lf\n",ans);
}

void init()
{
    scanf("%d %d\n",&N,&M);
    for(int i=1;i<=N;i++)
    {
        scanf("%d %d\n",&X[i],&Y[i]);
        InitUFS(i);
    }
    int a,b;
    for (int i=1;i<=M;i++)
    {
        scanf("%d %d\n",&a,&b);
        used[a][b]=true;
        used[b][a]=true;
        if(Find(a)!=Find(b))
        {
            Union(a,b);
            B++;
        }
    }
   
    if(B==N-1)
    {
        printf("%.2lf\n",ans);
        return;
    }
   
    double x;
    for (int i=1;i<=N;i++)
        for (int j=1;j<=N;j++)
            if(!used[i][j])
            {
                x=GetDist(i,j);
                if(x!=0)
                {
                    R[++top].s=i;
                    R[top].e=j;
                    R[top].len=x;
                }
            }
    qsort(R+1,top,sizeof(R[0]),cmp);
    Kruskal();
}

int main()
{
    freopen("roads.in","r",stdin);
    freopen("roads.out","w",stdout);
    init();
    fclose(stdin);
    fclose(stdout);
    return 0;
}

BYVoid大犇的代碼：

//最小生成树 Kruskal + 并查集
#include <iostream>
#include <cmath>
#define MAX 1001
using namespace std;
 
class tUFS
{
private:
 int F[MAX],Size;
 int findroot(int a)
 {
  int b=a,t;
  while (F[a]>0)
   a=F[a];
  while (F[b]>0)
  {
   t=F[b];
   F[b]=a;
   b=t;
  }
  return a;
 }
public:
 bool judge(int a,int b)
 {
  return F[findroot(a)]==F[findroot(b)];
 }
 void merge(int a,int b)
 {
  F[findroot(b)]=findroot(a);
 }
 tUFS(int N)
 {
  Size=N;
  for (int i=1;i<=N;i++)
   F[i]=-i;
 }
};
 
typedef struct
{
 int a,b;
 double v;
}edge;
 
typedef struct
{
 int x,y;
}point;
 
tUFS *U;
int N,M,C;
double Ans;
edge E[MAX*MAX];
point P[MAX];
 
void quicksort(int i,int j)
{
 int t1=i,t2=j;
 edge T,k=E[(i+j)/2];
 do
 {
  while (E[t1].v<k.v) t1++;
  while (E[t2].v>k.v) t2--;
  if (t1<=t2)
  {
   T=E[t1];
   E[t1]=E[t2];
   E[t2]=T;
 
   t1++;
   t2--;
  }
 }while (t1<t2);
 if (t2>i) quicksort(i,t2);
 if (t1<j) quicksort(t1,j);
}
 
inline double dist(point a,point b)
{
 return sqrt ( (double)(a.x-b.x)*(a.x-b.x) + (double)(a.y-b.y)*(a.y-b.y) );
}
 
void init()
{
 int i,j,a,b;
 freopen("roads.in","r",stdin);
 freopen("roads.out","w",stdout);
 scanf("%d%d",&N,&M);
 U=new tUFS(N);
 for (i=1;i<=N;i++)
  scanf("%d%d",&P[i].x,&P[i].y);
 for (i=1;i<=M;i++)
 {
  scanf("%d%d",&a,&b);
  if (!U->judge(a,b))
   U->merge(a,b);
 }
 for (i=C=1;i<=N-1;i++)
 {
  for (j=i+1;j<=N;j++,C++)
  {
   if (C==62375)
    C=C;
   E[C].a=i;
   E[C].b=j;
   E[C].v=dist(P[i],P[j]);
  }
 }
 C--;
 quicksort(1,C);
}
 
void kruskal()
{
 int i,cnt;
 for (i=1,cnt=0;i<=C && cnt<C-1-M;i++)
 {
  if (!U->judge(E[i].a,E[i].b))
  {
   U->merge(E[i].a,E[i].b);
   Ans+=E[i].v;
   cnt++;
  }
 }
}
 
int main()
{
 init();
 kruskal();
 printf("%.2lfn",Ans);
 return 0;
}

BYVoid大牛的代碼下載