【BZOJ 1016】[JSOI2008] 最小生成树计数

链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1016
优秀题解:https://blog.sengxian.com/solutions/bzoj-1016

题解

考虑最小生成树,如果使用价值相同的非树边边替换树边,得到的效果一定一样
因为不一样的话,用于替换的边就会成为最小生成树的树边
换一句话来说,权值相同的边处理完之后,图的连通性一定一样

于是暴力枚举同一权值的边的组合情况
使用并查集判断一下即可

代码

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100+9;
const int M = 1000+9;
const int MOD = 31011;

struct Edge{int u,v,w;}e[M];
vector<Edge> que[M];
int n,m,fa[N],fa_tmp[N],_hash[M],cnt[M],tot,vout=1,vis[N];

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 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;
}

void DFS(int w, int sz, int cur, int id, int &tmp) {
	if (cur > cnt[id]) {
		return ;
	} else if (w == sz + 1) {
		if (cur == cnt[id]) {
			memcpy(fa_tmp, fa, sizeof(fa));
			int i; for (i=1;i<=sz;i++) if (vis[i]) {
				if (find(que[id][i-1].u) == find(que[id][i-1].v)) break;
				fa[find(que[id][i-1].u)] = find(que[id][i-1].v);
			}	
			tmp += (i == sz + 1);
			memcpy(fa, fa_tmp, sizeof(fa));
		}
	} else {
		DFS(w+1, sz, cur, id, tmp);
		vis[w] = 1;
		DFS(w+1, sz, cur+1, id, tmp);
		vis[w] = 0;
	}
}

int main(){
	n = read(); m = read();
	for (int i=1,u,v;i<=m;i++) {
		e[i].u = u = read(); 
		e[i].v = v = read();
		_hash[i] = e[i].w = read();
	}
	sort(_hash+1, _hash+1+m);
	tot = unique(_hash+1, _hash+1+m) - _hash - 1;
	for (int i=1,tmp;i<=m;i++) {
		tmp = lower_bound(_hash+1, _hash+1+tot, e[i].w) - _hash;
		que[tmp].push_back(e[i]);
	}
	for (int i=1;i<=n;i++)
		fa[i] = i;
	for (int i=1;i<=tot;i++) {
		for (int j=que[i].size()-1;~j;j--) {
			if (find(que[i][j].u) != find(que[i][j].v)) {
				fa[find(que[i][j].u)] = find(que[i][j].v);
				cnt[i]++;
			}
		}
	} 
	for (int i=2;i<=n;i++) {
		if (find(i) != find(1)) {
			puts("0");
			exit(0);
		}
	}
	
	for (int i=1;i<=n;i++) 
		fa[i] = i;
	for (int i=1,tmp=0;i<=tot;i++,tmp=0) if (cnt[i]) {
		DFS(1,que[i].size(),0,i,tmp);
		for (int j=que[i].size()-1;~j;j--) 
			fa[find(que[i][j].u)] = find(que[i][j].v);
		(vout *= tmp) %= MOD;
	}
	printf("%d\n",vout);
	return 0;
}

288 thoughts to “【BZOJ 1016】[JSOI2008] 最小生成树计数”

  1. My coder is trying to persuade me to move to .net from PHP.
    I have always disliked the idea because of the expenses.
    But he’s tryiong none the less. I’ve been using Movable-type on several websites for about a year and
    am nervous about switching to another platform. I have heard fantastic things about blogengine.net.
    Is there a way I can import all my wordpress posts into
    it? Any kind of help would be greatly appreciated!

  2. Does your site have a contact page? I’m having a tough time
    locating it but, I’d like to shoot you an email.
    I’ve got some creative ideas for your blog you might be interested in hearing.
    Either way, great site and I look forward to seeing it grow over time.

  3. Greetings, I do believe your site could be having browser
    compatibility issues. Whenever I take a look at your
    web site in Safari, it looks fine however when opening in Internet Explorer, it has some
    overlapping issues. I merely wanted to give you a quick heads up!
    Apart from that, excellent site!

  4. When I originally commented I clicked the “Notify me when new comments are added” checkbox and now each
    time a comment is added I get several e-mails with the same comment.
    Is there any way you can remove me from that service?
    Thank you!

  5. Hey there just wanted to give you a quick heads up.
    The words in your article seem to be running off the screen in Firefox.
    I’m not sure if this is a format issue or something to do with browser compatibility but I figured I’d post to let you know.

    The style and design look great though! Hope you get the issue fixed soon. Kudos

  6. I do not even know how I stopped up here, however I believed this put up was
    great. I do not recognize who you are however definitely you are
    going to a well-known blogger for those who aren’t already.
    Cheers!

  7. This is really attention-grabbing, You’re an excessively professional blogger.
    I have joined your feed and stay up for looking for more of
    your magnificent post. Additionally, I have shared your web site in my social networks

  8. Hey I know this is off topic but I was wondering if you knew of any widgets I could add to my blog
    that automatically tweet my newest twitter updates.
    I’ve been looking for a plug-in like this for quite some time and was hoping maybe you would have some experience
    with something like this. Please let me know if you run into anything.
    I truly enjoy reading your blog and I look forward to
    your new updates.

  9. Hiya! Quick question that’s totally off topic. Do you know how to make your
    site mobile friendly? My weblog looks weird when browsing from
    my apple iphone. I’m trying to find a template or plugin that might be able to correct
    this problem. If you have any suggestions, please share. Thank you!

    natalielise plenty of fish

  10. We’re a gaggle of volunteers and starting a brand new scheme
    in our community. Your web site provided us with helpful info to work on.
    You’ve performed an impressive activity and our
    whole neighborhood might be grateful to you.

  11. It’s very straightforward to find out any matter on web as compared to books, as I found this paragraph at this website.
    plenty of fish natalielise

  12. Hi there very nice website!! Man .. Excellent .. Wonderful ..
    I’ll bookmark your web site and take the feeds also?
    I’m glad to find numerous helpful information here in the submit, we want develop more strategies in this
    regard, thanks for sharing. . . . . .

  13. I’m now not sure the place you are getting your information, however great topic.
    I needs to spend a while finding out much more or figuring
    out more. Thank you for great info I used to be in search of this info for my mission. natalielise plenty of fish

  14. Thank you for all of your work on this blog. Betty take interest in making time for research and it’s obvious why. My partner and i notice all about the dynamic tactic you provide vital tactics on this web blog and as well as invigorate contribution from other individuals on that theme and my princess is truly understanding a lot of things. Enjoy the rest of the new year. You are doing a useful job.

  15. Hello just wanted to give you a quick heads up and let you know a
    few of the pictures aren’t loading correctly. I’m not sure
    why but I think its a linking issue. I’ve tried it
    in two different internet browsers and both show the same outcome.

  16. I’m not sure where you’re getting your info, but great topic. I needs to spend some time learning more or understanding more. Thanks for great info I was looking for this info for my mission.

  17. Howdy would you mind letting me know which hosting company you’re working with?
    I’ve loaded your blog in 3 completely different browsers and I must say this blog loads
    a lot quicker then most. Can you suggest a good web hosting provider at a
    honest price? Thanks a lot, I appreciate it!

  18. Hey! This is kind of off topic but I need some help from an established blog.
    Is it difficult to set up your own blog? I’m not very techincal but I can figure things out pretty fast.
    I’m thinking about setting up my own but I’m not sure where to begin. Do
    you have any tips or suggestions? Thanks

  19. Simply desire to say your article is as astounding. The clarity in your submit is simply great and i could assume you are a professional on this subject. Well along with your permission let me to clutch your feed to keep updated with coming near near post. Thank you 1,000,000 and please keep up the gratifying work.|

  20. I feel that is one of the such a lot important info for me.
    And i am glad reading your article. However should remark on some basic issues, The website style is great, the articles is in point of fact great : D.
    Good process, cheers

  21. Sweet blog! I found it while searching on Yahoo News.
    Do you have any tips on how to get listed in Yahoo News? I’ve
    been trying for a while but I never seem to get there!
    Thanks

  22. Hello very nice blog!! Guy .. Excellent .. Wonderful ..

    I will bookmark your website and take the feeds additionally?

    I am satisfied to seek out so many useful information here within the post,
    we’d like develop more strategies in this regard, thanks for
    sharing. . . . . .

  23. Hmm it appears like your blog 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 writer but I’m still new to
    everything. Do you have any recommendations for newbie blog writers?
    I’d really appreciate it.

  24. Hi, i read your blog from time to time and i own a similar one and i was just curious if you get a lot of spam feedback? If so how do you prevent it, any plugin or anything you can suggest? I get so much lately it’s driving me crazy so any help is very much appreciated.|

  25. I’m impressed, I must say. Rarely do I encounter a
    blog that’s equally educative and interesting, and without a doubt, you have hit
    the nail on the head. The problem is an issue that too few men and women are speaking intelligently about.
    I am very happy I stumbled across this in my hunt
    for something concerning this.

  26. An intriguing discussion is worth comment. I do think that you ought to publish more on this subject matter, it may not be a taboo subject but typically people don’t speak about such topics.
    To the next! All the best!!

  27. I’m not that much of a online reader to be honest but your sites really nice, keep it up! I’ll go ahead and bookmark your website to come back down the road. Many thanks|

  28. I was curious if you ever thought of changing the structure of your site? Its very well written; I love what youve got to say. But maybe you could a little more in the way of content so people could connect with it better. Youve got an awful lot of text for only having 1 or 2 images. Maybe you could space it out better?|

  29. Hey there just wanted to give you a brief heads up and let you know a few of the pictures aren’t loading correctly. I’m not sure why but I think its a linking issue. I’ve tried it in two different internet browsers and both show the same outcome.|

  30. I truly love your blog.. Excellent colors & theme. Did you make this amazing site yourself? Please reply back as I’m planning to create my own website and would like to learn where you got this from or just what the theme is called. Cheers!|

  31. My brother suggested I may like this web site. He was once totally right. This post truly made my day. You cann’t imagine simply how much time I had spent for this information! Thank you!

  32. Nice blog! Is your theme custom made or did you download it
    from somewhere? A theme like yours with
    a few simple tweeks would really make my blog shine.
    Please let me know where you got your theme.
    Many thanks

  33. Greetings, I do believe your blog may be having web browser compatibility problems. When I take a look at your web site in Safari, it looks fine however when opening in IE, it’s got some overlapping issues. I simply wanted to provide you with a quick heads up! Apart from that, wonderful blog!|

  34. I’ll immediately grasp your rss as I can not in finding your email subscription link or e-newsletter service. Do you’ve any? Please let me recognise so that I may subscribe. Thanks.|

  35. Howdy! Someone in my Facebook group shared this website with us so I came to give it
    a look. I’m definitely enjoying the information. I’m bookmarking and will
    be tweeting this to my followers! Outstanding blog and terrific style and design.

  36. Yesterday, while I was at work, my sister stole my iPad and tested to see if it can survive a twenty five foot drop, just so she can be a youtube sensation. My iPad is now destroyed and she has 83 views. I know this is entirely off topic but I had to share it with someone!|

  37. Do you mind if I quote a few of your articles as long as I provide credit and sources back to your website? My website is in the very same niche as yours and my visitors would definitely benefit from some of the information you present here. Please let me know if this alright with you. Thanks!|

  38. Nice blog right here! Also your website quite a bit up fast! What web host are you the use of? Can I am getting your associate link in your host? I wish my web site loaded up as quickly as yours lol|

  39. Hi! I could have sworn I’ve visited this web site before but after going through some of the articles I realized it’s new to me. Nonetheless, I’m definitely happy I came across it and I’ll be bookmarking it and checking back regularly!|

  40. Excellent post. I was checking constantly this weblog and I am impressed! Very helpful information specifically the closing part 🙂 I take care of such information a lot. I used to be looking for this certain information for a very long time. Thanks and good luck.

  41. Hi there, You have done an excellent job. I will definitely digg it and personally suggest to my friends. I’m sure they’ll be benefited from this site.|

  42. Wow, awesome blog format! How long have you ever been running a blog for? you made running a blog glance easy. The entire glance of your website is fantastic, as neatly as the content material!

  43. Hi there would you mind letting me know which web
    host you’re working with? I’ve loaded your blog in 3 completely different browsers and I must say this blog loads a lot faster then most.
    Can you recommend a good hosting provider at a honest price?
    Thanks, I appreciate it!

  44. With havin so much content do you ever run into any issues of
    plagorism or copyright infringement? My blog has a lot of completely unique content
    I’ve either authored myself or outsourced but it
    looks like a lot of it is popping it up all over the web without my agreement.
    Do you know any techniques to help reduce content from being stolen? I’d really appreciate it.

  45. Excellent blog! Do you have any hints for aspiring writers?
    I’m hoping to start my own website soon but I’m a little lost
    on everything. Would you suggest starting with a free platform like WordPress or go
    for a paid option? There are so many choices out there that I’m totally overwhelmed ..

    Any ideas? Kudos!

  46. I’m now not positive where you are getting your info, but good topic.
    I must spend some time studying more or working out more.
    Thanks for great information I was on the lookout for this information for my mission.

  47. Have you ever thought about including a little bit more than just your articles?
    I mean, what you say is valuable and all. Nevertheless think of if you added some great
    visuals or video clips to give your posts more, “pop”! Your content is excellent but with pics and videos,
    this blog could undeniably be one of the very best in its field.
    Great blog!

  48. Do you mind if I quote a couple of your posts as long as I provide credit and sources back to your weblog?
    My blog site is in the exact same area of interest as yours and my visitors
    would truly benefit from some of the information you provide
    here. Please let me know if this ok with you. Thanks a
    lot!

  49. This is really interesting, You are a very skilled blogger.
    I’ve joined your rss feed and look forward to seeking more of your magnificent post.

    Also, I have shared your site in my social networks!

  50. hello!,I like your writing very a lot! proportion we keep in touch more approximately your article on AOL?

    I require a specialist on this house to solve my problem.
    Maybe that is you! Taking a look forward to see you.

  51. I just like the helpful information you provide to your articles.
    I’ll bookmark your blog and check once more right here regularly.
    I’m reasonably sure I’ll be told plenty of new stuff right right here!
    Good luck for the following!

  52. Heya i am for the first time here. I found this board and I find It truly useful & it helped me out a lot. I hope to give something back and aid others like you aided me.|

  53. Hello there! This article couldn’t be written any better!

    Reading through this post reminds me of my previous roommate!
    He always kept preaching about this. I’ll forward this post to him.

    Pretty sure he’s going to have a good read. Thanks for sharing!

  54. May I simply say what a relief to uncover someone that truly understands what they are talking about on the internet.
    You certainly understand how to bring a problem to light
    and make it important. More and more people
    ought to look at this and understand this side of your story.
    I can’t believe you’re not more popular given that you certainly
    have the gift.

  55. Hello there, You’ve performed a fantastic job. I’ll definitely digg it and in my opinion recommend to my friends. I’m sure they will be benefited from this site.|

  56. I’m really inspired along with your writing abilities as smartly as with the structure to your weblog. Is this a paid subject or did you modify it yourself? Either way stay up the excellent quality writing, it is uncommon to peer a nice weblog like this one these days..|

  57. You really make it seem so easy together with your presentation however I find this topic to be actually something which I believe I might by no means understand.

    It kind of feels too complicated and very wide for me.
    I am looking forward in your next post, I will attempt to get the hold of it!

  58. Thanks for some other fantastic article. The place else
    could anyone get that type of info in such a perfect
    means of writing? I’ve a presentation next week, and I’m at
    the look for such information.

  59. It’s good to come across a blog every once in a while that isn’t the same unswanted rehashed information. Excellent read! I’ve saved your site and I’m adding your RSS feeds to my Google account.

  60. You are so interesting! I do not believe I’ve read anything like that
    before. So good to discover someone with a few genuine thoughts on this issue.
    Seriously.. thank you for starting this up. This site is something that is needed on the web, someone
    with a little originality!

发表评论

电子邮件地址不会被公开。 必填项已用*标注