适合对并查集有一定理解的人. 新手可能看不懂吧....
并查集简单点说就是将相关的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 2 { 3 int r=x,t; r代表的是根节点 4 while(x!=flag[x]) 如果 没有找到 就继续追到根为止 5 x=flag[x]; 6 while(r!=x) 7 { //这里是相关优化 有个定义叫做秩就是类似于楼的层数 秩越低 你就越容易从楼顶走到楼底 将秩全部变成1即一层楼 8 t=flag[r]; 9 flag[r]=x; 10 r=t; 11 } 12 return x; 13 }
主要就是这个
最小生成树中 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[2100],ans,p[1005],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[15005]; int cmp(nood xx,nood yy) { return xx.w<yy.w; } int kruskal() { sort(pp,pp+m,cmp); memset(flag,0,sizeof(flag)); num=maxx=0; ans=1; for(int i=0; i<=n; i++) p[i]=i; for(int i=0; i<m; i++) { if(num==n-1) 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 0; } int main() { cin>>n>>m; for(int i=0; i<m; i++) cin>>pp[i].x>>pp[i].y>>pp[i].w; kruskal(); cout<<maxx<<endl<<num<<endl; for(int i=1; i<ans; i++) { cout<<flag[i]; if(i%2==0) cout<<endl; else cout<<" "; } return 0; } /* 一种输出 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=1; maxpath=maxxx=num=0; memset(value,0,sizeof(value)); memset(a,0,sizeof(a)); memset(flag,0,sizeof(flag)); //初始化相关参数 for(int i=2; i<=n; i++)//以 1 为起始点更新权值数组 { if(pp[1][i]!=maxx) value[i]=pp[1][i]; else value[i]=maxx; flag[i]=1; } flag[1]=0;//标记用过了.. //寻找剩下的 边 for(int i=2; i<=n; i++) { int k,min=maxx;//k作为下次扫描的点 for(int j=1; j<=n; j++) //依次扫描寻找与k即i相关联的 最小权值 { if(flag[j]!=0&&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]=0;//标记 //更新与上面相关的对应的权值 //(当这些权值小于上一次的就替换~重点!) //就这个实现了当有2个出发点的时候 //首出发点 相对应的小于第二个的 选择了首出发点 for(int j=2; j<=n; j++) { if(flag[j]!=0&&pp[k][j]<value[j]/*此处有无等号*/) { value[j]=pp[k][j]; flag[j]=k; } } } cout<<maxpath<<endl<<maxxx<<endl; for(int i=1; i<ans; i++) { cout<<a[i]; if(i%2!=0) cout<<" "; else cout<<endl; } return 0; } int main() { //freopen("a1.txt","r",stdin); //freopen("a11.txt","w",stdout); cin>>n>>m; //读入关联信息及其权值 memset(pp,maxx,sizeof(pp)); for(int i=1; i<=m; i++) { int x,y; cin>>x>>y; cin>>pp[x][y]; } prime(); return 0; }
或许会改....有空再说吧