Kruskal

啊哈磊

[code=Cpp width=740px]//Kruskal
#include <stdio.h>
struct node
{
        int x,y,len;
}e[1000];
int f[100]={0},n,m,k,sum;
int cmp(const void *x,const void *y)
{
        return (*(struct node *)x).len-(*(struct node *)y).len;
}
//这是找爹的递归函数，不停的去找爹，只到找到祖宗为止
int getf(int v)
{
        if(f[v]==v)
                return v;
        else
        {
                //这里是路径压缩，每次在函数返回的时候，顺带把路上遇到的人的祖宗都改为最后找到的祖宗的编号
                f[v]=getf(f[v]);
                return f[v];
        }
}
//这里是合并两子集合的函数，如果需要判断的两个节点，在不同的集合中
//我们就把右边的集合，作为左边集合的子集合，
void merge(int v,int u)
{
        int t1,t2;
        t1=getf(v);
        t2=getf(u);
        if( t1!=t2 )
        {
                f[t1]=t2;//经过路径压缩以后，将f的根的值也赋值为v的祖先f[t1]
        }
}
//判断连个点是否在一个集合中，不多说了，你懂的
int query(int v,int u)
{
        if(getf(v)==getf(u))
                return 1;
        else
                return 0;
}

//请从此处开始阅读程序，从主函数开始阅读程序是一个好习惯
int main()
{
        freopen("test.in","r",stdin);
        freopen("test.out","w",stdout);

        int i,x,y;
        scanf("%d %d",&n,&m);

        for(i=1;i <= m;i++)
        {
           scanf("%d %d %d", &e.x, &e.y, &e.len);
        }
        qsort(&e[1],m,sizeof(e[0]),cmp);

        for(i=1;i <= m;i++)
                printf("%d %d %d\n",e.x,e.y,e.len);

        printf("---\n");
        //初始化是必须的
        for(i=1;i <= n;i++)
                f=i;

        i=1;k=0;sum=0;
        while(k < n)
        {
                if( query(e.x,e.y)==0 )
                {
                        k++;
                        sum += e.len;
                        //开始集合的合并处理
                        merge(e.x,e.y);
                }
                i++;
        }

        printf("%d",sum);
        return 0;
}
[/code]

啊哈磊

有次看到某神牛短几行的代码：
——————————-
int getf(int v)
{
if (f[v] != v) f[v] = getf(f[v]);
return f[v];
}

int query(int v,int u)
{
return (getf(v) == getf(u));
}

邀请码

啊哈磊 发表于 2013-2-20 20:27
有次看到某神牛短几行的代码：
——————————-
int getf(int v)

并查集的核心代码，还有一句
int merge(int x,int y)
{
    a[getf(x)]=a[getf(y)];
}

邀请码

啊哈磊 发表于 2013-2-20 20:27
有次看到某神牛短几行的代码：
——————————-
int getf(int v)

并查集的核心代码，还有一句
int merge(int x,int y)
{
    a[getf(x)]=a[getf(y)];
}

邀请码

啊哈磊 发表于 2013-2-20 20:27
有次看到某神牛短几行的代码：
——————————-
int getf(int v)

并查集的核心代码，还有一句
int merge(int x,int y)
{
    a[getf(x)]=a[getf(y)];
}

邀请码

int die(int x)
{
    return father[x]==x?x:father[x]=find(father[x]);
}