【BZOJ 1415】[Noi2005] 聪聪和可可

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1415
数据生成器:http://paste.ubuntu.com/22417252/

论文题,记忆化深搜
我在处理该去哪时,用的三方的floyd
然而hzwer告诉我,平方的bfs就好QAQ,反正没有T,我就不改啦!(づ ̄ 3 ̄)づ

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN = 1000+9;
const int INF = 1000000;
const double sta = -0.5;

int n,m,C,M,d[MAXN][MAXN],to[MAXN][MAXN],cnt[MAXN];
double ans[MAXN][MAXN];

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

inline void Floyd(){
	for (int k=1;k<=n;k++) for (int i=1;i<=n;i++) if (d[i][k] < INF) 
		for (int j=1;j<=n;j++) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
	
	for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) for (int k=1;k<=n;k++) 
		if (d[i][k] == 1 && d[k][j] == d[i][j]-1) {to[i][j] = k; break;}
	for (int i=1;i<=n;i++) to[i][i] = i;
}

double Get_Ans(int u, int v){
	if (ans[u][v] > sta) return ans[u][v];
	else {
		if (to[to[u][v]][v] != v) {
			ans[u][v] = Get_Ans(to[to[u][v]][v],v)+1;
			for (int i=1;i<=n;i++) if (d[v][i] == 1) ans[u][v] += Get_Ans(to[to[u][v]][v],i)+1;
			return ans[u][v] /= cnt[v];
		} else return ans[u][v] = 1;
	}
}

int main(){ 
	n = read(); m = read(); C = read(); M = read();
	for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) d[i][j] = INF, ans[i][j] = -1;
	for (int i=1;i<=n;i++) d[i][i] = 0, ans[i][i] = 0, cnt[i] = 1;
	for (int i=1,a,b;i<=m;i++) cnt[a = read()]++, cnt[b = read()]++, d[a][b] = d[b][a] = 1;
	Floyd(); printf("%.3lf\n",Get_Ans(C,M));
	return 0;
} 

260 thoughts to “【BZOJ 1415】[Noi2005] 聪聪和可可”

  1. You could definitely see your enthusiasm in the
    work you write. The world hopes for more passionate writers like you who are not afraid to mention how they believe.
    All the time go after your heart.

  2. I have been exploring for a little bit for any high quality articles or blog posts on this
    sort of space . Exploring in Yahoo I ultimately stumbled upon this site.
    Studying this info So i’m glad to exhibit that I’ve an incredibly good uncanny feeling I came upon just what I needed.

    I so much indubitably will make sure to don?t forget this site and provides it a glance on a relentless basis.

  3. Someone necessarily help to make significantly articles I might state.

    This is the very first time I frequented your web page and thus far?
    I amazed with the research you made to create this particular put up extraordinary.
    Fantastic job!

  4. Its like you read my mind! You seem to know a lot about this, like you wrote the book in it or something.
    I think that you could do with some pics
    to drive the message home a bit, but instead of that, this is magnificent blog.
    A great read. I’ll definitely be back.

  5. whoah this blog is magnificent i really like reading your
    posts. Stay up the good work! You recognize, lots of people are searching
    around for this information, you could aid them greatly.

  6. I needed to thank you for this great read!! I absolutely enjoyed every little bit
    of it. I have you saved as a favorite to check out new things you post…

  7. First off I want to say wonderful blog! I had a quick question that I’d like to ask if you
    don’t mind. I was curious to know how you center yourself
    and clear your thoughts prior to writing. I’ve had a difficult time clearing
    my thoughts in getting my ideas out. I do take pleasure in writing
    but it just seems like the first 10 to 15 minutes are wasted simply
    just trying to figure out how to begin. Any suggestions or tips?
    Many thanks!

  8. That is really interesting, You’re an excessively skilled blogger.
    I have joined your rss feed and sit up for in the hunt
    for more of your wonderful post. Also, I’ve shared your website in my social
    networks

  9. Thanks for every other informative blog. The place else may just I get that kind of info written in such a perfect approach? I’ve a project that I’m just now running on, and I’ve been on the glance out for such information.

  10. My partner and I absolutely love your blog and
    find nearly all of your post’s to be what precisely I’m looking for.
    Would you offer guest writers to write content available for you?
    I wouldn’t mind producing a post or elaborating on a lot of
    the subjects you write about here. Again, awesome weblog!

  11. Hey there would you mind letting me know which webhost you’re working with?

    I’ve loaded your blog in 3 completely different internet browsers and I must
    say this blog loads a lot quicker then most. Can you recommend a good web hosting provider at a reasonable price?
    Kudos, I appreciate it!

  12. An impressive share! I’ve just forwarded this onto a friend who had been conducting a little
    homework on this. And he in fact bought me dinner because I found it for him…
    lol. So let me reword this…. Thank YOU for the meal!! But yeah, thanx for spending time to discuss this subject
    here on your internet site.

  13. This is the right site for anybody who really wants to
    find out about this topic. You understand so much
    its almost tough to argue with you (not that I actually will need to…HaHa).
    You definitely put a fresh spin on a subject which has been discussed for ages.
    Great stuff, just excellent!

  14. 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 four emails with the same comment. Is there any way you can remove me from that service? Thanks!

  15. You’ve made some decent points there. I looked on the web for more info about the issue and found most people will go along with your views on this website.|

  16. When someone writes an post he/she keeps the thought of a user in his/her mind that how a user can understand it. Therefore that’s why this post is great. Thanks!|

  17. Thanks , I have recently been searching for information about this subject for ages and yours is the greatest I’ve found out so far. However, what about the bottom line? Are you sure about the source?|

  18. I’ve been browsing online more than 2 hours today, yet I never found any interesting article like yours. It’s pretty worth enough for me. In my view, if all site owners and bloggers made good content as you did, the internet will be much more useful than ever before.|

  19. When I initially left a comment I appear to have clicked the -Notify me when new comments are added- checkbox and now each time a comment is added I receive 4 emails with the exact same comment. Is there an easy method you are able to remove me from that service? Cheers!|

  20. Hi there! This is kind of off topic but I need some help from an established blog. Is it very difficult to set up your own blog? I’m not very techincal but I can figure things out pretty fast. I’m thinking about creating my own but I’m not sure where to start. Do you have any ideas or suggestions? Thank you|

Leave a Reply

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