【Codeforces 715B】Complete The Graph

题目传送门:http://codeforces.com/contest/716/problem/D
官方题解:http://codeforces.com/blog/entry/47169

这题很好玩,有两种写法。

1)暴力最短路,复杂度O(nmlogn)
做法就是每一次找最短路,然后改一改

2)神奇二分,复杂度O(mlognlogm)
将可更改的边拉出来,排成一溜
二分一个点k,使1~k的边为1,其余边为INF
终止条件:k时最短路<=l,k-1时最短路>L
于是第k条边就是关键边,只用考虑这条边的长度即可
感觉好神!

考试的时候,我写的是第一种

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

const LL N = 1000+9;
const LL M = 20000+9;
const LL INF = 1e14;

LL head[N],to[M],nxt[M],cost[M],U[M],V[M],dis[N],n,m,L,S,T,sign[M],ty,inq[N],sur[N];
queue<LL> que;

inline LL read(){
	char c=getchar(); LL 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 Add_Edge(LL u, LL v, LL d) {
	static LL TT = 1;
	to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; cost[TT] = d;
	to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; cost[TT] = d;
}

inline LL SPFA(){
	for (int i=1;i<=n;i++) dis[i] = INF;
	dis[S] = 0; que.push(S), inq[S] = 1;
	
	while (!que.empty()) {
		LL w = que.front(); que.pop(); inq[w] = 0;
		for (LL i=head[w];i;i=nxt[i]) if (~cost[i] && dis[to[i]] > dis[w]+cost[i]) {
			dis[to[i]] = dis[w] + cost[i]; sur[to[i]] = i;
			if (!inq[to[i]]) que.push(to[i]), inq[to[i]] = 1;
		}
	} return dis[T];
}

int main(){
	n = read(); m = read(); L = read(); S = read() + 1; T = read() + 1;
	for (LL i=1,tmp;i<=m;i++) {
		U[i] = read()+1, V[i] = read()+1; tmp = read();
		if (!tmp) tmp = -1, sign[i] = 1;
		Add_Edge(U[i],V[i],tmp);
	}
	if (SPFA() < L) cout<<"NO", exit(0);
	for (LL i=1;i<=m;i++) if (sign[i]) cost[i*2] = cost[i*2+1] = 1;
	if ((ty=SPFA()) > L) cout<<"NO", exit(0);
	for (LL i=1;i<=m;i++) if (sign[i]) cost[i*2] = cost[i*2+1] = INF;
	LL w = T,len_tmp; while (w != S) {if(sign[sur[w]/2]) cost[sur[w]] = cost[sur[w]^1] = 1; w = to[sur[w]^1];}
	while ((len_tmp=SPFA()) < L) 
		for (w=T;w!=S;w=to[sur[w]^1]) if (sign[sur[w]/2]) {
			cost[sur[w]] += L - len_tmp, cost[sur[w]^1] += L - len_tmp; break;}
	cout<<"YES"<<endl;
	for (LL i=1;i<=m;i++) 
		if (sign[i] && cost[i*2] == -1) printf("%I64d %I64d %I64d\n",U[i]-1,V[i]-1,L+1);
		else printf("%I64d %I64d %I64d\n",U[i]-1,V[i]-1,cost[i*2]);
	return 0;
}

92 thoughts to “【Codeforces 715B】Complete The Graph”

  1. Hello there! This is kind of off topic but I need some advice from an established blog.
    Is it tough to set up your own blog? I’m not
    very techincal but I can figure things out pretty quick.
    I’m thinking about setting up my own but
    I’m not sure where to begin. Do you have any ideas or suggestions?
    Cheers

  2. whoah this weblog is excellent i really like studying your
    articles. Keep up the great work! You know, lots of individuals are hunting round for this information, you could aid them greatly.

  3. Howdy, i read your blog from time to time and i own a similar one
    and i was just wondering if you get a lot of spam responses?

    If so how do you prevent it, any plugin or anything you
    can recommend? I get so much lately it’s driving me insane so any assistance
    is very much appreciated.

  4. Hey there, I think your website might be having browser compatibility issues.

    When I look at your website in Firefox, it looks fine
    but when opening in Internet Explorer, it
    has some overlapping. I just wanted to give you a quick heads up!
    Other then that, wonderful blog!

  5. We’re a group of volunteers and starting a brand new scheme in our community.

    Your web site offered us with valuable info to work on. You’ve performed
    an impressive job and our whole group can be grateful to you.

  6. Attractive section of content. I just stumbled upon your
    blog and in accession capital to assert that I get in fact
    enjoyed account your blog posts. Any way I will be subscribing to your augment
    and even I achievement you access consistently fast.

  7. It is the best time to make some plans for the future and it’s time to be
    happy. I have read this post and if I could I want to suggest
    you some interesting things or advice. Maybe you could write next articles referring to this
    article. I desire to read even more things about it!

  8. Hi there very cool website!! Man .. Beautiful ..
    Amazing .. I’ll bookmark your site and take the feeds also?

    I am happy to find numerous helpful info
    right here within the publish, we want develop extra
    strategies in this regard, thank you for sharing.
    . . . . .

  9. 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 stop it, any plugin or anything you can recommend?

    I get so much lately it’s driving me mad so any support is very much appreciated.

  10. I would like to thank you for the efforts you have
    put in penning this website. I am hoping to view the same high-grade
    content from you later on as well. In fact, your creative writing abilities has
    encouraged me to get my own site now 😉

  11. Hello there, just became alert to your blog through Google, and found that it is really informative.
    I am going to watch out for brussels. I’ll appreciate if
    you continue this in future. Numerous people will be benefited from your writing.
    Cheers!

  12. Simply wish to say your article is as astonishing. The clarity on your
    put up is just nice and that i can suppose you are
    a professional on this subject. Fine along with your permission let me to snatch your RSS feed to stay updated with forthcoming post.

    Thank you a million and please keep up the gratifying work.

  13. Hi! Do you know if they make any plugins to help with SEO?

    I’m trying to get my blog to rank for some targeted keywords
    but I’m not seeing very good success. If you know of any please share.

    Kudos! natalielise pof

  14. You actually make it seem so easy with your presentation but I find this
    matter to be really something which I think I would never understand.

    It seems too complex and extremely broad for me.

    I am looking forward for your next post, I will
    try to get the hang of it!

  15. Hi there! Quick question that’s totally off topic.

    Do you know how to make your site mobile friendly? My site looks weird when browsing from my iphone.
    I’m trying to find a template or plugin that might
    be able to resolve this problem. If you have any suggestions, please share.
    Cheers!

  16. 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.

  17. I was more than happy to find this great site.
    I need to to thank you for ones time for this particularly wonderful read!!
    I definitely liked every part of it and I have you book-marked to see new things on your
    web site.

  18. Today, I went to the beach front with my children. I
    found a sea shell and gave it to my 4 year old daughter and said “You can hear the ocean if you put this to your ear.” She put the shell to
    her ear and screamed. There was a hermit crab inside
    and it pinched her ear. She never wants to go back!
    LoL I know this is totally off topic but I had to tell someone!

  19. Wonderful goods from you, man. I have understand your stuff
    previous to and you are just too great. I actually like what you’ve acquired
    here, certainly like what you are stating and the way in which you say it.
    You make it enjoyable and you still take care of to keep it sensible.

    I cant wait to read far more from you. This is actually a tremendous site.

  20. Hello there! I could have sworn I’ve visited this
    blog before but after looking at many of the posts I realized it’s new to me.
    Nonetheless, I’m certainly happy I stumbled upon it and
    I’ll be book-marking it and checking back frequently!

  21. naturally like your web-site however you need
    to test the spelling on quite a few of your posts.
    Several of them are rife with spelling problems and I in finding it
    very troublesome to tell the truth however I will definitely come again again.

  22. I’m now not certain the place you are getting your info, however
    great topic. I must spend a while learning more or figuring
    out more. Thanks for fantastic info I was on the lookout for this information for my mission.

  23. I was recommended this website by my cousin. I’m not sure
    whether this post is written by him as no one else know such detailed about my problem.
    You’re incredible! Thanks!

  24. 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 WordPress on a variety of 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 posts into it?
    Any kind of help would be really appreciated!

  25. Today, I went to the beachfront with my children. I found a sea shell and gave it to my 4 year
    old daughter and said “You can hear the ocean if you put this to your ear.” She
    placed the shell to her ear and screamed. There was a hermit crab inside and it pinched her ear.
    She never wants to go back! LoL I know this is totally off topic but I had to tell someone!

  26. Hello, i believe that i saw you visited my weblog so i got here to go back the desire?.I’m trying to find issues to
    enhance my site!I guess its ok to make use of some of your concepts!!

  27. Hi there! I just wanted to ask if you ever
    have any trouble 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 protect
    against hackers?

  28. An outstanding share! I have just forwarded this onto a coworker who
    had been conducting a little research on this.

    And he in fact bought me breakfast due to the fact that I discovered it for him…
    lol. So allow me to reword this…. Thank YOU for the meal!!
    But yeah, thanx for spending time to discuss this matter here on your web site.

  29. Hi there! I’m at work browsing your blog from my new iphone 3gs!
    Just wanted to say I love reading through your
    blog and look forward to all your posts! Carry on the fantastic work!

  30. Excellent items from you, man. I’ve take into account your stuff prior to
    and you’re just too magnificent. I really like what you’ve got right here,
    certainly like what you’re saying and the best way wherein you assert it.

    You make it entertaining and you continue to care for to stay it wise.
    I cant wait to learn much more from you. This is actually a
    wonderful site.

  31. Today, while I was at work, my cousin stole my iphone and tested
    to see if it can survive a 40 foot drop, just so she can be a youtube sensation. My iPad is now broken and she has 83 views.
    I know this is completely off topic but I had to share it with someone!

  32. Hey there! I realize this is sort of off-topic however I had to ask.

    Does running a well-established blog such as yours
    require a large amount of work? I am completely new to running
    a blog but I do write in my diary every day. I’d like to start a blog so I can easily share my
    personal experience and thoughts online. Please let me know if
    you have any ideas or tips for brand new aspiring blog owners.
    Appreciate it!

  33. You really make it seem so easy with your presentation but I
    find this matter to be actually something which I think
    I would never understand. It seems too complicated and extremely
    broad for me. I am looking forward for your next post,
    I’ll try to get the hang of it!

  34. Its such as you read my thoughts! You seem to understand
    so much approximately this, like you wrote the ebook in it or something.

    I believe that you simply can do with some % to pressure the message house a bit, but other than that, this
    is excellent blog. A fantastic read. I’ll certainly be back.

  35. We’re a group of volunteers and opening a new scheme in our community.
    Your web site offered us with valuable info to work on. You’ve done a formidable job and our whole community will be grateful to you.

  36. Hello this is somewhat 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 expertise
    so I wanted to get guidance from someone with experience.
    Any help would be enormously appreciated!

  37. Attractive component to content. I simply stumbled upon your blog and in accession capital to say that I
    get actually loved account your blog posts.
    Any way I will be subscribing to your feeds or even I achievement you access consistently fast.

  38. Thanks a bunch for sharing this with all people you really recognise
    what you are speaking about! Bookmarked. Kindly also discuss with my website =).
    We may have a hyperlink exchange contract between us

  39. 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 can do with a few pics to drive the message home a little bit, but other than that, this is wonderful blog. A great read. I’ll certainly be back.

  40. Fantastic website. Plenty of helpful info here. I’m sending it to some friends ans also sharing in delicious.
    And certainly, thank you in your effort!

  41. Hi there outstanding website! Does running a blog such as this take
    a lot of work? I’ve absolutely no understanding of programming but I had been hoping to start my own blog
    soon. Anyhow, should you have any recommendations or techniques for new blog owners
    please share. I know this is off topic nevertheless
    I just wanted to ask. Appreciate it!

  42. Howdy! Someone inn mmy Facebook group shared this website with us so I came to check
    it out. I’m definitely enjoying the information. I’m book-marking and will be tweeting this to my followers!
    Exceptiknal blog and wonderful style andd design.

  43. I blog often and I seriously thank you for your content.
    Your article has really peaked my interest. I am going to bookmark your blog and
    keep checking for new information about once per week.
    I opted in for your RSS feed as well.

  44. Wow, superb blog layout! How long have you been blogging for?
    you made blogging look easy. The overall look of your site is
    wonderful, as well as tthe content!

  45. I must thank you for the efforts you’ve put in penning this website.
    I am hoping to see the same high-grade content from
    you later on as well. In fact, your creative writing abilities has encouraged me to get my own, personal blog now 😉

  46. Fantastic goods from you, man. I’ve understand your suff previous tto and you’re just extremely wonderful.
    I really like what you’ve acquired here, really like wht you are saying and the way iin which you say it.
    Youu make it enjoyable and you still take care of to keep itt
    wise. I cant wait to reead far more frm you. Thiss is
    really a tremendous website.

  47. Oh my goodness! Amazing article dude! Many thanks, However I am hzving troubles
    with your RSS. I don’t understand the reason why I am unable too join it.
    Is there anybody else getting similar RSS problems?
    Anybody who knows the answer will you kindly respond? Thanks!!

  48. Hey there I am so thrilled I found your web site,
    I really found you by mistake, while I was searching on Yahoo for
    something else, Regardless I am here now and would just like to say cheers for
    a incredible post and a all round enjoyable blog (I also love the theme/design), I don’t
    have time to read it all at the minute but I have bookmarked
    it and also included your RSS feeds, so when I have time I will be back to read much
    more, Please do keep up the awesome b.

Leave a Reply

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