参考例题: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/
I am in fact grateful to the holder of this web site who has shared
this impressive paragraph at here.
I quite like reading through an article that will make people think.
Also, thank you for allowing me to comment!
Hi, after reading this amazing paragraph i am too happy to share
my know-how here with mates.
Keep this going please, great job!
Since the admin of this website is working, no doubt very rapidly it
will be well-known, due to its feature contents.
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.
I’m gone to tell my little brother, that he should also pay a visit this weblog on regular basis to obtain updated from latest information.
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?
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!
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.
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!
I’ve recently started a site, the info you offer on this site has helped me greatly. Thank you for all of your time & work.
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!
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.
. . . . .
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!
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.
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.
This post will assist the internet people for setting up
new web site or even a blog from start to end.
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.
Thanks for finally writing about >【模板库】Borůvkas algorithm – Qizy’s
Database <Liked it!
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!
Very energetic post, I enjoyed that bit. Will there be a
part 2?
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.
I think you have remarked some very interesting points, thanks for the post.