【模板库】Borůvka’s algorithm

参考例题:http://www.lydsy.com/JudgeOnline/problem.php?id=2429
参考代码:

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#define pow(x) ((x)*(x))
using namespace std;

const int N = 1000+9;
const int M = 1000000+9;
const double EPS = 1e-8;

int X[N],Y[N],to[M],nxt[M],head[N],val[N],tot,n,m,vout,fa[N],cot[N];
double w[M],cpt[N],MX;

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline void AddEdge(int i, int j){
	double tmp = sqrt(pow(X[i]-X[j])+pow(Y[i]-Y[j]));
	to[++m] = j; nxt[m] = head[i]; w[m] = tmp; head[i] = m;
	to[++m] = i; nxt[m] = head[j]; w[m] = tmp; head[j] = m;
}

inline int find(int w){
	int f=fa[w],tmp;
	while (fa[f] != f) f = fa[f];
	while (w != f) tmp=fa[w],fa[w]=f,w=tmp;
	return f;
}

inline void Boruvka(){
	for (int i=1;i<=n;i++) fa[i] = i;
	for (int t=n;t>1;) {
		memset(cot,0,sizeof(cot));
		for (int i=1,f1,f2;i<=n;i++) for (int j=head[i];j;j=nxt[j]){
			f1 = find(i); f2 = find(to[j]);
			if (f1 != f2) {
				if (!cot[f1] || cpt[f1] > w[j]) cot[f1] = f2, cpt[f1] = w[j];
				if (!cot[f2] || cpt[f2] > w[j]) cot[f2] = f1, cpt[f2] = w[j];
			} 	
		}
		
		for (int i=1,ft;i<=n;i++) if (fa[i] == i) {
			if ((ft = find(cot[i])) != i) {
				fa[ft] = i; MX = max(MX, cpt[i]); t--;
			}
		} 
	}
}

int main(){
	tot=read(); for (int i=1;i<=tot;i++) val[i] = read();
	n = read(); for (int i=1;i<=n;i++) {
		X[i] = read(); Y[i] = read();
		for (int j=1;j<i;j++) AddEdge(i,j);
	}
	Boruvka();
	for (int i=1;i<=tot;i++) if (EPS+val[i] >= MX) vout++;
	printf("%d\n",vout);
	return 0;
}

算法简介:https://en.wikipedia.org/wiki/Bor%C5%AFvka%27s_algorithm
算法正确性证明:http://oi.cyo.ng/wp-content/uploads/2016/08/02345678641.png
国外带注释模板:http://www.geeksforgeeks.org/greedy-algorithms-set-9-boruvkas-algorithm/

24 thoughts to “【模板库】Borůvka’s algorithm”

  1. Its like you read my mind! You appear to know so much about this, like you
    wrote the book in it or something. I think that you can do with a
    few pics to drive the message home a little bit, but instead of that, this is fantastic blog.
    A great read. I will definitely be back.

  2. Remarkable things here. I’m very glad to look your article.
    Thank you so much and I’m taking a look ahead to touch
    you. Will you kindly drop me a e-mail?

  3. Howdy! This post couldn’t be written any better!
    Reading this post reminds me of my old room mate! He always kept talking
    about this. I will forward this write-up to
    him. Fairly certain he will have a good read.
    Thank you for sharing!

  4. Great post. I used to be checking continuously this weblog and I’m impressed!
    Extremely useful information particularly the final part :
    ) I handle such info a lot. I was looking for this certain info for
    a very long time. Thanks and best of luck.

  5. Hi there! This is my 1st comment here so I just wanted
    to give a quick shout out and tell you I genuinely enjoy reading your
    posts. Can you recommend any other blogs/websites/forums that go over the same topics?

    Thanks a ton!

  6. You’re so interesting! I do not suppose I’ve read through a single thing like this before.

    So great to discover another person with a few original
    thoughts on this topic. Seriously.. many thanks for starting this up.
    This web site is something that is needed on the web, someone with some originality!

  7. Howdy very nice web site!! Guy .. Beautiful .. Amazing .. I’ll bookmark your blog and
    take the feeds additionally? I’m happy to seek out numerous helpful info here
    within the put up, we’d like work out more techniques on this regard, thank you for sharing.
    . . . . .

  8. Wow, wonderful blog layout! How long have you been blogging for?

    you made blogging look easy. The overall look of your web site
    is fantastic, let alone the content!

  9. May I simply say what a relief to discover someone that actually
    understands what they are talking about on the web.
    You definitely realize how to bring a problem to light and
    make it important. More people should look at this and understand this side of your story.
    I was surprised you’re not more popular given that you certainly have the gift.

  10. Do you have a spam problem on this blog; I also am a blogger, and
    I was wondering your situation; we have developed some nice methods
    and we are looking to trade strategies with others, please shoot me an email if interested.

  11. Ahaa, its fastidious conversation regarding this post at this place at this website,
    I have read all that, so at this time me also commenting here.

  12. My brother suggested I might like this website. He was once totally right.
    This put up truly made my day. You can not imagine just how much time I had
    spent for this info! Thank you!

  13. After looking at a few of the blog articles on your web site, I honestly appreciate your way of blogging.
    I added it to my bookmark webpage list and will be checking back soon. Please visit my web site too and let me know
    how you feel.

Leave a Reply to sling tv asksylphoflight Cancel reply

Your email address will not be published. Required fields are marked *