之前也写过Kruskal算法,到今天才发现 原来以前的写错了。(也不能说完全错,只是效率好低)。
以前忽视的地方主要有两点,一是Kruskal算法,一般先对边从小到大排好序,然后从小到大区边。
这样的话,排完序以后就只要一个循环就可以走完。
二是 并查集的路径压缩,我以前对并查集合并是遍历所有的结点对两个集合合并,
而正确的做法应该是这样
int flindfather(int a) { if(a==father[a]) return a; else return findfather(father[a]); }
而其实我们还可以进行路径压缩,这才是并查集的核心所在
只要将上面的代码改写一行,就能起到很好的效果
int flindfather(int a) { if(a==father[a]) return a; else return father[a]=findfather(father[a]); }
下面是1861的代码
#include<iostream> #include <algorithm> using namespace std; #define MAXSIZE 30010 #define INF 9000100 int n,m; int father[MAXSIZE];//并查集 int head[MAXSIZE]; int next[MAXSIZE]; int e; struct node{ int u; int v; int w; }; node edge[MAXSIZE]; node medge[MAXSIZE]; int num; int ansmax,anstot; //判断两点是否属于同一集合 int judge(int a,int b) { if(father[a]==father[b])//同一集合 return 1; return 0; } bool cmp(node &a,node &b) { return a.w<b.w; } int findset(int a) { if(a==father[a]) return a; else return father[a]=findset(father[a]); } void kruskal() { sort(edge,edge+e,cmp); int i,j; num=0; ansmax=anstot=0; for(i=0;i<2*m;i++) father[i]=i; //初始时 每个元素属于不同的集合 for(i=0;i<2*m;i++) { if(findset(edge[i].u)!=findset(edge[i].v))//如果不属于同一集合 { ansmax=ansmax>edge[i].w?ansmax:edge[i].w; medge[num++]=edge[i]; int tu=edge[i].u;//将所有与v一个集合的全部并入u的集合 int tv=edge[i].v; father[findset(tv)]=findset(tu); } } } void addnode(int u,int v,int w) { edge[e].u=u; edge[e].v=v; edge[e].w=w; next[e]=head[u]; head[u]=e++; } int main() { //freopen("in.txt","r",stdin); while(scanf("%d%d",&n,&m)!=EOF) { e=0; int t1=m; while(t1--) { int a,b,c; scanf("%d%d%d",&a,&b,&c); addnode(a,b,c); addnode(b,a,c); } kruskal(); printf("%d\n",ansmax); printf("%d\n",num); for(int i=0;i<num;i++) printf("%d %d\n",medge[i].u,medge[i].v); } }
相关推荐
北大POJ初级-图算法 解题报告+AC代码
北大POJ初级-基本算法 解题报告+AC代码
北大POJ中级-基本算法 解题报告+AC代码
北大POJ2002-Squares 解题报告+AC代码
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码
poj 1000 - 2000 部分题目 官方分类 poj 1000 - 2000 部分题目 官方分类
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ3020-Antenna Placement 解题报告+AC代码
这是魔兽世界终极版POJ的-测试数据,找了好久才找到的。 本来想设置为0积分,但是它居然自动收费(o_ _)ノ。 看传送门:https://pan.baidu.com/s/1cCIwW8psGDASu2JdZawG3Q
北大POJ3414-Pots 解题报告+AC代码
POJ3211--Washing Clothes
北大POJ2305-Basic remains POJ2305-Basic remains
北大POJ1321-Chess Problem POJ1321-Chess Problem
北大POJ1080-Human Gene Functions POJ1080-Human Gene Functions
POJ---1456.Supermarket测试数据及答案,题目描述:A supermarket has a set Prod of products on sale. It earns a profit px for each product x∈Prod sold by a deadline dx that is measured as an integral ...
poj 1000-3000部分代码 网上收集
POJ 1038--Bugs Integrated
POJ3036--Honeycomb Walk
北大POJ1159-Palindrome 解题报告+AC代码
北大POJ3273-Monthly Expense POJ3273-Monthly Expense