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
#include
#include
#include
#include
using namespace std;
const int MAX_SIZE=800;
struct Node
{
int u,v;
double w;
bool operator < (const Node a)const
{
return 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 if(getflag(edge[i].u)!=getflag(edge[i].v))
{
flag[getflag(edge[i].u)]=flag[getflag(edge[i].v)];
cout< }
}

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
#include
#include
#include
#include
using namespace std;
const int MAX_SIZE=800;
struct Node
{
int u,v;
double w;
bool operator < (const Node a)const
{
return 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 if(getflag(edge[i].u)!=getflag(edge[i].v))
{
flag[getflag(edge[i].u)]=flag[getflag(edge[i].v)];
cout< }
}

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;
}