题目大意:n个点由m条边连接(1.两点之间最多1条边连接;2.点不能连接自身;3.至少有一种方式连接所有的点)。求出一个方案,使这个方案能用最小的长度连接所有的顶点。
输入:第一行:n(2<=n<=1000),m(1<=m<=15000);
            后面m行:a(顶点1),b(顶点2),c(长度)。
输出:第一行:方案中最长的边
            第二行:方案中边的数目(永远都是n-1)
            后面n-1行:方案中间的边(顶点表示)
解题思路:
1.最小生成树,用kruskal做。
2.先将所有的边按权值从小到大排序,然后一次选择加入。加入的时候判断是否生成回路,不生成则加入,否则判断下一条。
3.判断回路用并查集。
数据结构:

typedef struct
{
	int a;
	int b;
	int c;
}graph;//图

typedef struct
{
	int x;
	int y;
}outv;//输出的边

核心代码:

sort(g+1,g+m+1,cmp);
    cnt=0;
    for(i=1;i<=m;i++)
	{
		curx=find(g[i].a);
		cury=find(g[i].b);
        if(curx!=cury)
		{
            if(g[i].c>minc)
				minc=g[i].c;
			ov[cnt].x=g[i].a;
			ov[cnt].y=g[i].b;
            parent[curx]=cury;
			cnt++;
        }
    }

find函数

int find(int x){
	while(x!=parent[x]){
		x=parent[x];
	}
	return x;
}

发表评论

电子邮件地址不会被公开。

Post Navigation