【Codeforces 757F】Team Rocket Rises Again

相关链接

题目传送门:http://codeforces.com/problemset/problem/757/F
官方题解:http://codeforces.com/blog/entry/49743
中文题面及题解:https://blog.sengxian.com/solutions/cf-757f

解题报告

先搞出一个最短路径树,然后把一些非树边也给搞进来
我们发现这货是一个DAG,那么问题就转化为了:

给定一个DAG,问删掉一个点,最多使得多少点不可到达

然后我们就会想起这个题:BZOJ 2851
于是我们搞一个灾难树就可以啦!

Code

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

const int N = 200000+9;
const int M = 600000+9;
const LL INF = 1e9 * 1e9;

LL dis[N];
int n,m,s,E,vout,fa[N][20],done[N],in[N];
int head[N],to[M],nxt[M],cost[M],dep[N]; 
priority_queue<pair<LL,int> > que;
vector<int> anc[N],son[N];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	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 Add_Edge(int u, int v, int c = 0) {
	to[++E] = v; nxt[E] = head[u]; head[u] = E; cost[E] = c;
	to[++E] = u; nxt[E] = head[v]; head[v] = E; cost[E] = c;
}

inline void Dijkstra() {
	memset(dis,60,sizeof(dis)); 
	dis[s] = 0; que.push(make_pair(0, s));
	
	while (!que.empty()) {
		int w = que.top().second; que.pop(); 
		if (!done[w]) done[w] = 1;
		else continue;
		for (int i=head[w];i;i=nxt[i]) {
			if (dis[to[i]] > dis[w] + cost[i]) {
				dis[to[i]] = dis[w] + cost[i];
				que.push(make_pair(-dis[to[i]], to[i]));
			}
		}
	}
}

inline int LCA(int u, int v) {
	if (dep[u] < dep[v]) swap(u, v);
	for (int i=19;~i;i--) if (dep[fa[u][i]] >= dep[v]) u = fa[u][i];
	if (u == v) return u;
	for (int i=19;~i;i--) if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
	return fa[u][0];
}

void solve(int w) {
	done[w] = 1;
	int f = anc[w][0];
	for (int i=1;i<(int)anc[w].size();i++) 
		f = LCA(f, anc[w][i]);
	Add_Edge(f, w);
	fa[w][0] = f; dep[w] = dep[f] + 1;
	for (int i=1;i<20;i++)
		fa[w][i] = fa[fa[w][i-1]][i-1];
	for (int i=son[w].size()-1,t;~i;i--) {
		t = son[w][i];
		if (--in[t] == 0 && !done[t]) {
			solve(t);
		}
	}
}

int DFS(int w, int f) {
	int sz = 1;
	for (int i=head[w];i;i=nxt[i]) {
		if (to[i] != f) {
			sz += DFS(to[i], w);
		}
	}
	if (w != s) vout = max(vout, sz);
	return sz;
}

int main() {
	n = read(); m = read(); s = read();
	for (int i=1,u,v;i<=m;i++) {
		u = read(); v = read();
		Add_Edge(u, v, read());
	}
	Dijkstra(); 
	for (int w=1;w<=n;w++) {
		if (dis[w] > INF) continue;
		for (int i=head[w];i;i=nxt[i]) {
			if (dis[to[i]] == dis[w] + cost[i]) {
				anc[to[i]].push_back(w);
				son[w].push_back(to[i]);
				in[to[i]] += (w != s);
			}
		}
	}
	memset(head,0,sizeof(head));
	memset(done,0,sizeof(done));
	done[s] = 1; E = 0;
	for (int i=0;i<20;i++) fa[s][i] = s;
	for (int i=1;i<=n;i++) {
		if (!in[i] && !done[i] && dis[i] < INF) {
			solve(i);
		}
	}
	DFS(s, s);
	printf("%d\n",vout);
	return 0;
}

215 thoughts to “【Codeforces 757F】Team Rocket Rises Again”

  1. First off I want to say fantastic blog! I had a quick question that I’d like to ask
    if you don’t mind. I was curious to find out how you
    center yourself and clear your mind prior to writing.
    I’ve had trouble clearing my thoughts in getting my thoughts out.
    I do take pleasure in writing however it just seems like the first
    10 to 15 minutes are generally lost simply just
    trying to figure out how to begin. Any recommendations or tips?
    Cheers!

  2. I really like your blog.. very nice colors & theme.

    Did you design this website yourself or did you hire someone to
    do it for you? Plz reply as I’m looking to design my own blog and would like
    to find out where u got this from. cheers

  3. Hi! I know this is kinda off topic but I’d figured I’d ask.
    Would you be interested in trading links or maybe guest authoring a blog article or vice-versa?
    My website covers a lot of the same subjects as yours and I think we
    could greatly benefit from each other. If you happen to be interested feel free to shoot me an e-mail.
    I look forward to hearing from you! Awesome blog by the way!

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

  5. It’s a shame you don’t have a donate button! I’d without a doubt donate to this
    brilliant blog! I suppose for now i’ll settle for bookmarking and adding your RSS
    feed to my Google account. I look forward to fresh updates and will share this website
    with my Facebook group. Talk soon!

  6. Simply want to say your article is as astounding.
    The clearness for your submit is just cool and i can assume you are
    an expert on this subject. Fine along with your permission let me to snatch your
    feed to stay up to date with drawing close post. Thank you a million and please
    continue the rewarding work.

  7. You’re so interesting! I don’t suppose I’ve truly read anything like that before.

    So wonderful to find someone with some genuine thoughts on this subject.
    Seriously.. thank you for starting this up.
    This web site is one thing that is required on the internet, someone with a little originality!

  8. Hey there fantastic website! Does running a blog such as this require a massive amount work?
    I have very little expertise in programming but I was hoping to start my own blog soon. Anyways, if you have any recommendations or techniques for new blog owners please share.

    I know this is off subject but I just needed to ask.
    Thanks!

  9. You are so interesting! I do not suppose I’ve truly
    read something like this before. So wonderful to find another person with
    some original thoughts on this subject. Really.. thank you for
    starting this up. This site is something that is needed on the web,
    someone with a bit of originality!

  10. Hi there! Someone in my Myspace group shared this site with us so
    I came to give it a look. I’m definitely loving the information. I’m book-marking and
    will be tweeting this to my followers! Exceptional blog and outstanding design and style.
    plenty of fish natalielise

  11. May I just say what a relief to discover someone that actually
    knows what they are discussing on the internet. You actually understand how to bring an issue to light and make it important.
    More people must look at this and understand this side of the story.
    It’s surprising you aren’t more popular given that
    you definitely possess the gift.

  12. What’s up to all, the contents existing at this site are truly awesome for people knowledge, well, keep up the good work fellows.
    natalielise plenty of fish

  13. Hi, i think that i saw you visited my site thus i came to “return the favor”.I’m attempting to find things to improve my web site!I
    suppose its ok to use a few of your ideas!!

  14. It’s truly a nice and helpful piece of info.
    I’m happy that you just shared this useful info with us.
    Please keep us informed like this. Thank you for sharing.

  15. My programmer is trying to convince me to move to .net from
    PHP. I have always disliked the idea because of the costs.
    But he’s tryiong none the less. I’ve been using Movable-type on several websites for about a year and am worried about switching
    to another platform. I have heard fantastic things about blogengine.net.
    Is there a way I can import all my wordpress content into it?
    Any help would be really appreciated! natalielise plenty
    of fish

  16. wonderful publish, very informative. I ponder why the opposite specialists of this sector don’t understand
    this. You must continue your writing. I’m sure, you have a huge readers’
    base already!

  17. Can I just say what a comfort to uncover someone that actually understands
    what they are talking about on the net. You actually realize how to bring an issue to light and make it
    important. More and more people need to read this and understand this side of your story.
    I was surprised you aren’t more popular
    because you certainly possess the gift.

  18. I think that is among the such a lot important information for me.
    And i am glad studying your article. However want to observation on few
    general things, The website style is ideal, the articles is in reality
    nice : D. Excellent job, cheers

  19. An intriguing discussion is worth comment. I think that you need to publish more about
    this issue, it might not be a taboo matter but typically people do not discuss such topics.
    To the next! All the best!!

  20. You really make it appear so easy with your presentation but I find this topic to be actually one thing
    that I believe I’d never understand. It kind of feels too complex and
    extremely wide for me. I’m having a look forward to your subsequent publish,
    I’ll attempt to get the hang of it!

  21. Heya i’m for the first time here. I found this board and I
    find It really useful & it helped me out much. I hope to give something back and aid others like you helped me.

  22. You are so cool! I do not suppose I have read a single thing like that before. So wonderful to find another person with unique thoughts on this topic. Seriously.. many thanks for starting this up. This website is something that is required on the internet, someone with a bit of originality!|

  23. With havin so much content and articles do you ever run into any issues of plagorism or copyright infringement?
    My website 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 prevent content from being stolen? I’d certainly appreciate it.

  24. Have you ever thought about creating an ebook or guest authoring on other websites?

    I have a blog based on the same subjects you discuss and would really like to have you share some stories/information. I know
    my visitors would value your work. If you’re even remotely interested, feel free to
    shoot me an e mail.

  25. Heya i’m for the primary time here. I came across this board and I find It
    truly useful & it helped me out a lot. I’m hoping to present something back
    and aid others like you helped me.

  26. I just want to mention I’m beginner to weblog and honestly enjoyed your website. Likely I’m want to bookmark your blog . You surely have exceptional articles. Thanks a lot for sharing with us your blog.

  27. My brother recommended I might like this web site. He was totally right. This post truly made my day. You can not imagine just how much time I had spent for this information! Thanks!

  28. There are some attention-grabbing cut-off dates on this article but I don’t know if I see all of them middle to heart. There’s some validity however I’ll take hold opinion till I look into it further. Good article , thanks and we would like more! Added to FeedBurner as nicely

  29. My coder is trying to convince 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 a variety of websites for about a year and am nervous about switching to another platform. I have heard excellent things about blogengine.net. Is there a way I can import all my wordpress posts into it? Any help would be greatly appreciated!|

  30. I¡¦ve been exploring for a little bit for any high-quality articles or weblog posts in this kind of space . Exploring in Yahoo I finally stumbled upon this site. Studying this information So i¡¦m happy to show that I have an incredibly good uncanny feeling I found out just what I needed. I so much unquestionably will make sure to do not put out of your mind this web site and give it a glance on a constant basis.

  31. Palletized UK Goods Storage for International Shoppers, International shipping, Shipping items, Shipping items on a pallet, too heavy, too large, normal parcel, shipping palletized goods, international destination, packing a pallet, Palletized UK goods, Storage for international shoppers, Shipping service from the UK, Shipping service

  32. Howdy! I simply would like to give you a big thumbs up for your excellent information you have right here on this post. I am returning to your web site for more soon.

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

  34. This is the perfect site for anyone who would like to understand this topic.
    You understand a whole lot its almost tough to argue
    with you (not that I personally would want to…HaHa).
    You definitely put a brand new spin on a topic that’s been discussed for decades.
    Great stuff, just excellent!

  35. certainly like your web site but you need to check the spelling on several of your posts. Many of them are rife with spelling problems and I find it very troublesome to tell the truth nevertheless I will definitely come back again.

  36. There are definitely lots of particulars like that to take into consideration. That may be a great level to deliver up. I provide the thoughts above as basic inspiration however clearly there are questions like the one you carry up the place crucial factor might be working in trustworthy good faith. I don?t know if greatest practices have emerged round things like that, however I’m sure that your job is clearly recognized as a fair game. Each boys and girls feel the affect of only a second’s pleasure, for the rest of their lives.

  37. Its like you read my mind! You appear 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 excellent blog. A fantastic
    read. I’ll definitely be back.

  38. Good day! This is kind of off topic but I need some guidance 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 setting up my own but I’m not sure
    where to start. Do you have any points or suggestions?
    Thanks

  39. Hello there. I discovered your site by the use of Google at the same time as looking for a comparable subject, your site came up. It looks great. I’ve bookmarked it in my google bookmarks to visit then.

  40. HiHelloHi thereWhat’s up, I log on tocheckread your new stuffblogsblog regularlylike every weekdailyon a regular basis. Your story-tellingwritinghumoristic style is awesomewitty, keep doing what you’re doingup the good workit up!

  41. Great blog here! Also your website loads up very fast! What web host
    are you using? Can I get your affiliate link to your host?
    I wish my site loaded up as quickly as yours lol

  42. Hey! I just wanted to ask if you ever have any problems with hackers?
    My last blog (wordpress) was hacked and I ended up losing
    several weeks of hard work due to no data backup. Do you have any solutions to stop hackers?

  43. Hiya, I’m really glad I have found this information. Nowadays bloggers publish only about gossip and internet stuff and this is really frustrating. A good web site with exciting content, that’s what I need. Thanks for making this website, and I’ll be visiting again. Do you do newsletters by email?

  44. This is very interesting, You are a very professional blogger.
    I’ve joined your feed and stay up for in search of extra of your fantastic
    post. Also, I have shared your web site in my
    social networks

  45. I’m more than happy to uncover this website. I wanted to thank you for ones time just for
    this fantastic read!! I definitely appreciated every little bit of it
    and i also have you saved to fav to see new things on your site.

  46. I really love your site.. Very nice colors & theme.

    Did you create this site yourself? Please reply back as I’m hoping to create
    my own blog and would like to learn where you got this from or exactly what the theme is named.
    Thanks!

  47. Have you ever thought about adding a little bit more than just
    your articles? I mean, what you say is fundamental
    and everything. Nevertheless think about if you added some great pictures or video clips to give your posts more, “pop”!
    Your content is excellent but with images and video clips, this blog
    could certainly be one of the most beneficial in its niche.

    Amazing blog!

  48. 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!) Fantastic job.
    I really loved what you had to say, and more than that, how you presented it.

    Too cool!

  49. I like the helpful info you provide in your articles. I will bookmark your blog and check again here regularly. I am quite certain I’ll learn plenty of new stuff right here! Good luck for the next!

  50. Hello there! This article could not be written any better!
    Looking at this article reminds me of my previous roommate!
    He constantly kept preaching about this. I will forward this article to him.
    Pretty sure he will have a great read. Thank you for
    sharing!

  51. Hiya, I am really glad I have found this information. Today bloggers publish just about gossip and net stuff and this is really annoying. A good web site with interesting content, this is what I need. Thank you for making this web site, and I’ll be visiting again. Do you do newsletters by email?

  52. Thanks a lot for providing individuals with a very wonderful opportunity to read critical reviews from this website. It is always so terrific plus stuffed with a lot of fun for me and my office fellow workers to search your website more than 3 times per week to find out the newest guidance you will have. Of course, we’re usually astounded with all the eye-popping guidelines you serve. Certain two tips in this article are unequivocally the most beneficial I’ve ever had.

  53. Hello there. I discovered your blog by way of Google whilst looking for a similar subject, your website came up. It looks good. I’ve bookmarked it in my google bookmarks to come back then.

  54. Awesome write-up. I am a normal visitor of your web site and appreciate you taking the time to maintain the nice site. I will be a frequent visitor for a really long time.

  55. Hi, i think that i saw you visited my web siteso i came to return the want?.I am attemptingto in finding things to improve my website!I guess its good enough to make use of someof your ideas!!

  56. Hello, I do think your site could possibly be having web browser compatibility issues.
    Whenever I look at your website in Safari, it looks fine however when opening in Internet Explorer,
    it has some overlapping issues. I just wanted to give
    you a quick heads up! Besides that, excellent site!

  57. Hey there! I’ve been reading your weblog for a long time now
    and finally got the courage to go ahead and give you
    a shout out from Dallas Texas! Just wanted to mention keep up the great job!

  58. Heya just wanted to give you a brief heads up and let you know a few of the images 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 results.

  59. Hiya, I’m really glad I’ve found this information. Today bloggers publish just about gossip and internet stuff and this is actually irritating. A good site with exciting content, that is what I need. Thanks for making this web site, and I will be visiting again. Do you do newsletters by email?

  60. Hello there. I discovered your blog via Google even as searching for a similar subject, your site came up. It appears good. I have bookmarked it in my google bookmarks to come back then.

  61. I have been absent for some time, but now I remember why I used to love this website. Thanks , IЎ¦ll try and check back more frequently. How frequently you update your site?

  62. Hi there. I found your website by the use of Google whilst looking for a related subject, your website got here up. It looks good. I’ve bookmarked it in my google bookmarks to come back then.

  63. I’m not sure where you’re getting your information, but great topic.

    I needs to spend some time learning much more or understanding more.
    Thanks for fantastic information I was looking for this information for my mission.

  64. I’а†ve read several excellent stuff here. Certainly value bookmarking for revisiting. I wonder how a lot attempt you put to make this type of magnificent informative site.

  65. Thank you a bunch for sharing this with all folks you actually understand what you are talking about!Bookmarked. Kindly additionally talk over with my site =).We could have a hyperlink change arrangement among us

  66. I’m impressed, I need to say. Really not often do I encounter a blog that’s both educative and entertaining, and let me let you know, you may have hit the nail on the head. Your concept is outstanding; the issue is something that not enough people are talking intelligently about. I am very comfortable that I stumbled throughout this in my seek for one thing referring to this.

  67. Woah! I’m really digging the template/theme of this blog.It’s simple, yet effective. A lot of times it’s tough to get that“perfect balance” between user friendliness and visual appeal.I must say you’ve done a excellent job with this.In addition, the blog loads super quick for me on Safari.Exceptional Blog!

  68. Thanks for the sensible critique. Me & my neighbor were just preparing to do a little research about this. We got a grab a book from our local library but I think I learned more clear from this post. I’m very glad to see such magnificent info being shared freely out there.

  69. Awesome write-up. I’m a normal visitor of your website and appreciate you taking the time to maintain the excellent site. I will be a frequent visitor for a really long time.

  70. Hey there. I found your site by way of Google while looking for a related matter, your website got here up. It seems to be good. I have bookmarked it in my google bookmarks to come back then.

  71. Hiya, I am really glad I’ve found this info. Nowadays bloggers publish just about gossip and internet stuff and this is actually annoying. A good blog with exciting content, that’s what I need. Thanks for making this web site, and I’ll be visiting again. Do you do newsletters by email?

Leave a Reply

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