适合对并查集有一定理解的人. 新手可能看不懂吧....
并查集简单点说就是将相关的2个数字联系起来
比如
房子 1 2 3 4 5 6
能通向的房子 2 3 4 5 6 1
主要 建立并查集的 函数结构 模板(一般不变除非加权--最好能理解)
for(int i=0;i<n;i++)
flag[i]=i; //标记数组初始化以方便寻根
1 int find(int x) X相当于1
{
int r=x,t; r代表的是根节点
while(x!=flag[x]) 如果 没有找到 就继续追到根为止
x=flag[x];
while(r!=x)
{ //这里是相关优化 有个定义叫做秩就是类似于楼的层数 秩越低 你就越容易从楼顶走到楼底 将秩全部变成1即一层楼
t=flag[r];
flag[r]=x;
r=t;
}
return x;
}
主要就是这个
最小生成树中 keruskai()
核心思想: 将所有元素按照某一标志 排序 然后从最前开始一次检索寻根如果
二者没有相同的根就说明他们是第一次相互关联 然后把它们的权加到value上
举例 : 你要把3个房间打通来让 别人 可以去任意房间..
这些房间没有房顶你能飞到任意房间去砸墙 但是他们的关联情况不同并且 花费的费用也不同
你要使他们的费用最低
1. A B 10万元
2. B C 20万元
3. A C 30万元 你可以
1,2 30
1,3 40
2,3 50
显然选择 1,2
就用上面的kruskal
排序后 先是 a-b 判断是否有相同根(打通?)没有 就打通 10万元 然后
b-c 判断是否有相同的根 没有就打通 然后继续判断
a-c 判断已经打通了 跳过...
(当然也可以加一个sum统计打通情况3个房间 2个通道就行 打通一次sum++;当sum=n-1直接跳过节省时间)
最小生成树中prime();
简单点说就是用一个二维数组记录用坐标对应 他的权(距离/价值) 然后从第第一个起点扫描和他链接的其他点
中的权值并加入一个新的数组 找到权值最小的点就是所求的,标记他,然后从他权值最小对应的点开始扫描和他相关联的点
如果比之前 存权呢个数组小就更新为新的值(重点重点重点----)具体看例题代码的
例题 poj 1861 [ http://poj.org/problem?id=1861 ]
2种解法(kruskal(克鲁斯卡尔)这个过了 ,prime 表示没过(输出感觉没有问题..)
建议..用kruskal
据说简单的快,复杂的prime快) 上代码
kruskal()
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int flag[],ans,p[],n,m,maxx,num;
int find(int a)
{
int r=a,tmp;
while(r!=p[r])
r=p[r];
while(a!=r)
{
tmp=p[a];
p[a]=r;
a=tmp;
}
return r;
}
struct nood
{
int x,y,w;
} pp[];
int cmp(nood xx,nood yy)
{
return xx.w<yy.w;
}
int kruskal()
{
sort(pp,pp+m,cmp);
memset(flag,,sizeof(flag));
num=maxx=;
ans=;
for(int i=; i<=n; i++)
p[i]=i;
for(int i=; i<m; i++)
{
if(num==n-)
break;
int xxx=find(pp[i].x);
int yyy=find(pp[i].y);
if(xxx!=yyy)
{
p[xxx]=yyy;
flag[ans++]=pp[i].x;
flag[ans++]=pp[i].y;
maxx=max(pp[i].w,maxx);
num++;
}
}
return ;
}
int main()
{
cin>>n>>m;
for(int i=; i<m; i++)
cin>>pp[i].x>>pp[i].y>>pp[i].w;
kruskal();
cout<<maxx<<endl<<num<<endl;
for(int i=; i<ans; i++)
{
cout<<flag[i];
if(i%==)
cout<<endl;
else
cout<<" ";
}
return ;
} /* 一种输出
1 3
1 3
2 3
2 4 输入数据
4 6
1 2 1
1 3 1
1 4 2
2 3 1
3 4 1
2 4 1 */
prime();
不知道为啥WR
代码
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#define maxx 1200
using namespace std;
int n,m,pp[maxx][maxx],value[maxx],flag[maxx],maxpath,num,a[maxx],maxxx;
int prime()
{
int ans=;
maxpath=maxxx=num=;
memset(value,,sizeof(value));
memset(a,,sizeof(a));
memset(flag,,sizeof(flag));
//初始化相关参数
for(int i=; i<=n; i++)//以 1 为起始点更新权值数组
{
if(pp[][i]!=maxx)
value[i]=pp[][i];
else
value[i]=maxx;
flag[i]=;
}
flag[]=;//标记用过了..
//寻找剩下的 边
for(int i=; i<=n; i++)
{
int k,min=maxx;//k作为下次扫描的点
for(int j=; j<=n; j++) //依次扫描寻找与k即i相关联的 最小权值
{
if(flag[j]!=&&min>value[j])
{
min=value[j];
k=j;
}
}
//更新相关参数
maxpath=max(maxpath,value[k]);
maxxx+=value[k];
a[ans++]=flag[k];
a[ans++]=k;
num++;
flag[k]=;//标记
//更新与上面相关的对应的权值
//(当这些权值小于上一次的就替换~重点!)
//就这个实现了当有2个出发点的时候
//首出发点 相对应的小于第二个的 选择了首出发点
for(int j=; j<=n; j++)
{
if(flag[j]!=&&pp[k][j]<value[j]/*此处有无等号*/)
{
value[j]=pp[k][j];
flag[j]=k;
}
}
}
cout<<maxpath<<endl<<maxxx<<endl;
for(int i=; i<ans; i++)
{
cout<<a[i];
if(i%!=)
cout<<" ";
else
cout<<endl;
}
return ;
}
int main()
{
//freopen("a1.txt","r",stdin);
//freopen("a11.txt","w",stdout);
cin>>n>>m;
//读入关联信息及其权值
memset(pp,maxx,sizeof(pp));
for(int i=; i<=m; i++)
{
int x,y;
cin>>x>>y;
cin>>pp[x][y];
}
prime();
return ;
}
或许会改....有空再说吧