poj 1751 Highways 最小生成樹之Kruskal（克魯斯卡爾）算法

大意是一個有n個城市的國家，已知有些城市有道路聯通，問增加哪些道路使得所有的城市都可以彼此聯通且代價最小，已經代價是兩個城市坐標的笛卡爾距離；

就是一個純粹的找最小生成樹的題；

首先講所有邊按權值從小到大排序，然後依次取最小邊，如果聯通的兩個節點在兩個聯通分量上，則加入這條邊，否則刪除這條邊；

kruskal算法的要點就是判斷兩個節點是不是在一個聯通分量上，於是夠著個標記數組flag[]；開始時候令flag[i]=i;這樣就所有的節點都是一個聯通分量，然後在取已有的m條邊時，

設邊鏈接的節點為u,v,則令f[u]=f[v];就行了，這樣兩個節點就在一個聯通分量上了，不過操作的時候不是f[u]=f[v]這麼簡單，因為必須使u在的聯通分量和v在的聯通分量聯通起來，所以每個聯通分量裡的節點的flag值可以指向同一個節點，具體的操作見下面代碼：

此題輸出邊的時候沒有要求順序；

參考代碼如下：

[cpp]
#include<iostream>  
#include<cstring>  
#include<algorithm>  
#include<cstdlib>  
#include<cmath>  
using namespace std; 
const int MAX_SIZE=800; 
struct Node 
{ 
    int u,v; 
    double w; 
    bool operator < (const Node a)const 
    { 
        return w<a.w; 
    }; 
}edge[MAX_SIZE*MAX_SIZE/2]; 
struct point 
{ 
    int x,y; 
}a[MAX_SIZE]; 
int flag[MAX_SIZE],num,n,m; 
 
int getflag(int u) 
{ 
    if(flag[u]!=u) 
        flag[u]=getflag(flag[u]); 
    return flag[u]; 
} 
void execute() 
{ 
    int i,j; 
    for(i=1;i<=n;i++) 
    { 
        for(j=i+1;j<=n;j++) 
            if(getflag(i)!=getflag(j)) 
            { 
                edge[num].u=i; 
                edge[num].v=j; 
                edge[num++].w=sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y)); 
            } 
    } 
    sort(edge,edge+num); 
    for(i=0;i<num;i++) 
        if(getflag(edge[i].u)!=getflag(edge[i].v)) 
        { 
            flag[getflag(edge[i].u)]=flag[getflag(edge[i].v)]; 
            cout<<edge[i].u<<' '<<edge[i].v<<endl; 
        } 
} 
 
int main() 
{ 
    cin>>n; 
    int u,v; 
    int i; 
    for(i=1;i<=n;i++) 
        cin>>a[i].x>>a[i].y; 
    cin>>m; 
    for(i=1;i<=n+2;i++) 
    flag[i]=i; 
    num=0; 
    while(m--) 
    { 
        cin>>u>>v; 
        flag[getflag(u)]=flag[getflag(v)]; 
    } 
    execute(); 
    return 0; 
} 

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
using namespace std;
const int MAX_SIZE=800;
struct Node
{
    int u,v;
    double w;
    bool operator < (const Node a)const
    {
        return w<a.w;
    };
}edge[MAX_SIZE*MAX_SIZE/2];
struct point
{
    int x,y;
}a[MAX_SIZE];
int flag[MAX_SIZE],num,n,m;

int getflag(int u)
{
    if(flag[u]!=u)
        flag[u]=getflag(flag[u]);
    return flag[u];
}
void execute()
{
 int i,j;
 for(i=1;i<=n;i++)
 {
  for(j=i+1;j<=n;j++)
   if(getflag(i)!=getflag(j))
   {
    edge[num].u=i;
    edge[num].v=j;
    edge[num++].w=sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y));
   }
 }
 sort(edge,edge+num);
 for(i=0;i<num;i++)
  if(getflag(edge[i].u)!=getflag(edge[i].v))
  {
   flag[getflag(edge[i].u)]=flag[getflag(edge[i].v)];
   cout<<edge[i].u<<' '<<edge[i].v<<endl;
  }
}

int main()
{
 cin>>n;
 int u,v;
 int i;
 for(i=1;i<=n;i++)
  cin>>a[i].x>>a[i].y;
 cin>>m;
 for(i=1;i<=n+2;i++)
 flag[i]=i;
 num=0;
 while(m--)
 {
  cin>>u>>v;
  flag[getflag(u)]=flag[getflag(v)];
 }
 execute();
 return 0;
}