关于最小生成树(并查集)prime和kruskal

时间:2023-01-20 21:35:06

适合对并查集有一定理解的人.  新手可能看不懂吧....

并查集简单点说就是将相关的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;
}

 

或许会改....有空再说吧