poj1861 kruskal

简介: http://poj.org/problem?id=1861 #include<cstdio> #include<algorithm> #include<cstdlib> using namespace std; #define maxn 1001 #define maxm 15001 struct edge { int u,v

http://poj.org/problem?id=1861

#include<cstdio>
#include<algorithm>
#include<cstdlib>
using namespace std;
#define maxn 1001
#define maxm 15001
struct edge
{
    int u,v,w;
} edges[maxm];
int parent[maxn],ans[maxn];
int i,j,N,M;
int maxedge,num,ai;
void ufset()
{
    for(i=0; i<N; i++)
        parent[i]=-1;
}
int find(int x)
{
    int s;
    for(s=x; parent[s]>=0; s=parent[s]);
    while(s!=x)
    {
        int tmp=parent[x];
        parent[x]=s;
        x=tmp;
    }
    return s;
}
void Union(int R1,int R2)
{
    int r1=find(R1),r2=find(R2);
    int tmp=parent[r1]+parent[r2];
    if(parent[r1]>parent[r2])
    {
        parent[r1]=r2;
        parent[r2]=tmp;
    }
    else
    {
        parent[r2]=r1;
        parent[r1]=tmp;
    }
}
int cmp(const void* a,const void* b)
{
    edge aa=*(const edge*)a;
    edge bb=*(const edge*)b;
    return aa.w-bb.w;
}
void kruskal()
{
    int u,v;
    ufset();
    for(i=0; i<M; i++)
    {
        u=edges[i].u;
        v=edges[i].v;
        if(find(u)!=find(v))
        {
            ans[ai++]=i;
            if(edges[i].w>maxedge)
                maxedge=edges[i].w;
            num++;
            Union(u,v);
        }
        if(num>N-1)
            break;
    }
}
int main()
{
    //freopen("1.txt","r",stdin);
    while(scanf("%d%d",&N,&M)!=EOF)
    {
        for(i=0; i<M; i++)
            scanf("%d%d%d",&edges[i].u,&edges[i].v,&edges[i].w);
        qsort(edges,M,sizeof(edges[0]),cmp);
        maxedge=0;  num=0;
        kruskal();
        printf("%d\n%d\n",maxedge,num);
        for(i=0; i<num; i++)
            printf("%d %d\n",edges[ans[i]].u,edges[ans[i]].v);
    }
    return 0;
}

  

目录
相关文章
|
6月前
Poj 3255(dijkstra求次短路)
Poj 3255(dijkstra求次短路)
42 0
HDU-1874,畅通工程续(Floyd最短路)
HDU-1874,畅通工程续(Floyd最短路)
POJ-2253,Frogger(最短路问题)
POJ-2253,Frogger(最短路问题)
|
人工智能 并行计算 网络架构
|
人工智能 机器学习/深度学习 算法
【HDU 4463 Outlets】最小生成树(prim,kruscal都可)
以(x,y)坐标的形式给出n个点,修建若干条路使得所有点连通(其中有两个给出的特殊点必须相邻),求所有路的总长度的最小值。 因对所修的路的形状没有限制,所以可看成带权无向完全图,边权值为两点间距离。因是稠密图,故用邻接矩阵存储更好(完全图,边数e达到n(n-1)/2)。
1004 0