题目传送门:http://acm.split.hdu.edu.cn/showproblem.php?pid=5627
吐槽:HDU你好好的,为什么要加一个split?你TM还会分身了?
本来以为是位运算生成树,结果不是QAQ
管他的,看都看到了就来练练手
结果居然被这种题目给卡常了,cin在HDU上真是慢得一逼╮(╯▽╰)╭
#include<iostream> #include<cstdio> using namespace std; const int N = 300000+9; struct Edge{int u,v,val;}e[N]; int n,m,fa[N]; inline int find(int w){ int f=fa[w],tmp; while (f != fa[f]) f = fa[f]; while (w != f) tmp = fa[w], fa[w] = f, w = tmp; return f; } inline bool test(int x) { x = 1<<x-1; int tag = n-1; for (int i=1;i<=n;i++) fa[i] = i; for (int i=1;i<=m;i++) if (e[i].val & x) if (find(e[i].u) == find(e[i].v)) continue; else fa[find(e[i].u)] = find(e[i].v), tag--; if (!tag) { int tmp=0; for (int i=1;i<=m;i++) if (e[i].val & x) e[++tmp] = e[i]; m = tmp; return true; } else return false; } inline int read(){ char c=getchar(); int ret=0; while (c<'0'||c>'9') c=getchar(); while (c<='9'&&c>='0') ret=ret*10+c-'0', c=getchar(); return ret; } int main(){ int T; cin>>T; while (T--) { cin>>n>>m; int tag = n-1, vout = 0; for (int i=1;i<=n;i++) fa[i] = i; for (int i=1;i<=m;i++) { e[i].u = read(); e[i].v = read(); e[i].val = read(); if (find(e[i].u) == find(e[i].v)) continue; else fa[find(e[i].u)] = fa[find(e[i].v)], tag--; } if (tag) printf("0\n"); else { for (int i=31;i;i--) if (test(i)) vout |= 1<<i-1; printf("%d\n",vout); } } return 0; }
Hmm it appears like your site ate my first comment (it was extremely long) so I
guess I’ll just sum it up what I had written and say, I’m thoroughly enjoying your blog.
I too am an aspiring blog blogger but I’m still new to the whole thing.
Do you have any recommendations for rookie blog writers?
I’d certainly appreciate it.
whoah this weblog is fantastic i really like studying your posts.
Stay up the good work! You know, a lot of persons are hunting round for this
info, you could help them greatly.
I don’t know whether it’s just me or if perhaps everybody else encountering issues with your website.
It looks like some of the written text on your content are running off the screen. Can someone
else please comment and let me know if this is happening to them as well?
This could be a issue with my browser because I’ve had this happen previously.
Appreciate it
What’s up everyone, it’s my first go to see at this website, and paragraph is
genuinely fruitful in favor of me, keep up posting these types of posts.
I like the valuable information you provide in your articles.
I’ll bookmark your weblog and check again here regularly.
I’m quite certain I will learn plenty of new stuff right here!
Good luck for the next!
I am extremely impressed with your writing skills as well as with the layout on your weblog.
Is this a paid theme or did you modify it yourself?
Anyway keep up the excellent quality writing, it is rare to see a
nice blog like this one today.
Hello colleagues, good post and good urging commented here,
I am actually enjoying by these.
It’s nearly impossible to find experienced people
about this topic, however, you seem like you know what you’re talking about!
Thanks
Good day! I know this is kinda off topic but I’d figured I’d ask.
Would you be interested in exchanging links or maybe guest authoring
a blog post or vice-versa? My website goes over a lot of the same subjects as yours and I feel we could greatly
benefit from each other. If you might be interested feel free to
shoot me an email. I look forward to hearing from you!
Wonderful blog by the way!
For newest information you have to go to see world-wide-web and on web I found this web page as a best website for newest updates.
I am sure this post has touched all the internet people, its really really good piece of writing on building up
new website.
Fantastic goods from you, man. I have remember your stuff previous to and you’re simply extremely wonderful.
I actually like what you have got right here, certainly like what you are stating and the way through
which you say it. You make it enjoyable and you continue to
take care of to keep it wise. I cant wait to learn far
more from you. That is really a wonderful website.
F*ckin’ amazing things here. I’m very satisfied to look your article. Thank you a lot and i’m having a look ahead to touch you. Will you kindly drop me a mail?
Hey! I’m at work surfing around your blog from my new iphone 4!
Just wanted to say I love reading through your blog and look forward
to all your posts! Keep up the superb work!
I always used to study post in news papers but now as I am a user
of internet thus from now I am using net for articles, thanks to web.
I think the admin of this website is really
working hard for his site, as here every stuff is quality based stuff.
Heya this is kinda of off topic but I was wondering if blogs use WYSIWYG editors or if you have to manually code with HTML.
I’m starting a blog soon but have no coding experience so I wanted
to get guidance from someone with experience.
Any help would be greatly appreciated!
It’s going to be finish of mine day, however before
ending I am reading this fantastic paragraph to improve my know-how.
Ahaa, its fastidious conversation concerning this paragraph at this place at this weblog,
I have read all that, so now me also commenting at this place.
It’s amazing in support of me to have a web site, which is good in favor of my know-how.
thanks admin
Way cool! Some extremely valid points! I appreciate you penning this article and also
the rest of the website is also really good.
The other day, while I was at work, my sister stole my iphone and
tested to see if it can survive a twenty five foot drop, just so she can be a
youtube sensation. My apple ipad is now destroyed
and she has 83 views. I know this is entirely off topic but I had to
share it with someone!
This design is wicked! You obviously know how to keep a reader entertained.
Between your wit and your videos, I was almost moved
to start my own blog (well, almost…HaHa!) Wonderful job.
I really enjoyed what you had to say, and more than that, how
you presented it. Too cool!
I was very happy to search out this web-site.I wished to thanks to your time for this wonderful read!! I undoubtedly enjoying every little little bit of it and I’ve you bookmarked to check out new stuff you weblog post.