【BZOJ 2095】[Poi2010] Bridges

Qizy 二分, 其他, 图论, 欧拉回路 / 竞赛图, 网络流, 解题报告

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2095

这个题目啊！瞄一眼就知道是二分吧？
接下来就是给你一些有向边&无向边，让你判断是否存在欧拉回路

对于有向边，没有悬念，直接记录对于出度入度的贡献
只与有向边嘛，不妨先随便定一个向，然后考虑使用网络流进行调整
具体细节可以参见：http://blog.csdn.net/wzq_qwq/article/details/48651379

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int N = 2000+9;
const int M = 10000+9;
const int INF = 1e9;

struct Edge{int u,v,w1,w2;}edge[M];
int n,m,MX,MN=INF,in[N],out[N],cur[M];
int S,T,dis[N],flow[M],head[N],nxt[M],to[M],TT; 
queue<int> que;

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 void Add_Edge(int u, int v, int f) {
	to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = f;
	to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = 0;
} 

inline bool BFS(){
	memset(dis,-1,sizeof(dis));
	dis[S] = 0; que.push(0);
	
	while (!que.empty()) {
		int w = que.front(); que.pop();
		for (int i=head[w];i;i=nxt[i]) if (flow[i] && !~dis[to[i]]) {
			dis[to[i]] = dis[w] + 1;
			que.push(to[i]);
		}
	}
	
	return ~dis[T];
}

int DFS(int w, int f) {
	if (w == T) {
		return f;
	} else {
		int ret = 0;
		for (int &i=cur[w],tmp;i && f;i=nxt[i]) { 
			if (dis[to[i]] == dis[w] + 1) {
				tmp = DFS(to[i], min(f, flow[i]));
				ret += tmp; f -= tmp;
				flow[i] -= tmp; flow[i^1] += tmp;
			}
		}
		return ret;
	}
}

inline int Dinic(){
	int ret = 0;
	while (BFS()) {
		memcpy(cur,head,sizeof(head));
		ret += DFS(S,INF);
	}
	return ret;
}

inline bool judge(int lim){
	memset(in,0,sizeof(in));
	memset(out,0,sizeof(out));
	memset(head,0,sizeof(head));
	S = 0; T = N - 1; TT = 1;
	int tot = 0;
	
	for (int i=1;i<=m;i++) {
		if (lim < edge[i].w1) {
			continue;
		} else if (lim < edge[i].w2) {
			in[edge[i].v]++;
			out[edge[i].u]++;
		} else {
			in[edge[i].v]++;
			out[edge[i].u]++;
			Add_Edge(edge[i].u, edge[i].v, 2);
		}
	}
	
	for (int i=1;i<=n;i++) {
		if (abs(in[i]-out[i]) & 1) {
			return false;
		} else if (in[i] < out[i]) {
			Add_Edge(S,i,out[i]-in[i]);	
			tot += out[i] - in[i];
		} else if (in[i] > out[i]) {
			Add_Edge(i,T,in[i]-out[i]);
		}
	}
	
	return Dinic() == tot;
}

int main(){
	n = read(); m = read();
	for (int i=1;i<=m;i++) {
		edge[i].u = read();
		edge[i].v = read();
		edge[i].w1 = read();	
		edge[i].w2 = read();
		if (edge[i].w1 > edge[i].w2) {
			swap(edge[i].w1, edge[i].w2);
			swap(edge[i].u, edge[i].v);
		}
		MX = max(MX, edge[i].w2);
		MN = min(MN, edge[i].w1);
	}
	
	int l = MN, r = MX, mid, ret = -1;
	while (l <= r) {
		mid = l + r >> 1;
		if (judge(mid)) ret = mid, r = mid - 1;
		else l = mid + 1;
	}
	if (~ret) printf("%d\n",ret);
	else puts("NIE");
	return 0;
}

252 thoughts to “【BZOJ 2095】[Poi2010] Bridges”

  1. I’m amazed, I must say. Seldom do I encounter a blog that’s
    both educative and interesting, and let me tell you, you have
    hit the nail on the head. The issue is something which too few people are speaking intelligently about.
    I am very happy I came across this during my hunt for something regarding this.

    Reply

  2. What’s Taking place i am new to this, I stumbled upon this I
    have found It positively useful and it has helped me out loads.
    I am hoping to contribute & aid other customers like
    its helped me. Great job.

    Reply

  4. It’s very straightforward to find out any topic on net as compared to books, as I found this article at this website.

    Reply

  5. Howdy 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.

    Reply

  9. I do not even know the way I ended up here, however I thought this post was
    once great. I don’t recognise who you’re however certainly you are going to a well-known blogger in the event you are not already.

    Cheers!

    Reply

  11. Hello, Neat post. There is an issue together with your
    web site in web explorer, could check this? IE still is the marketplace
    chief and a big part of folks will miss your wonderful writing because of this problem.

    Reply

  12. I’m really enjoying the design and layout of your blog. It’s a very easy on the eyes which makes
    it much more enjoyable for me to come here and visit more often. Did you hire out a
    designer to create your theme? Great work!

    Reply

  17. Wonderful goods from you, man. I’ve understand your
    stuff previous to and you’re just extremely fantastic.
    I actually like what you have acquired here, really like what you’re stating and the way in which you say
    it. You make it entertaining and you still take care of to keep
    it smart. I cant wait to read far more from you. This is really a tremendous site.

    Reply

  19. Howdy just wanted to give you a quick heads up. The words in your post seem
    to be running off the screen in Chrome. I’m not sure if this is a format
    issue or something to do with web browser compatibility
    but I figured I’d post to let you know. The layout look great though!
    Hope you get the problem solved soon. Cheers

    Reply

  24. Hello this is somewhat of off topic but I was wanting to know if blogs use WYSIWYG editors or if you have to manually code with HTML.
    I’m starting a blog soon but have no coding knowledge so I wanted
    to get advice from someone with experience.
    Any help would be greatly appreciated! natalielise
    plenty of fish

    Reply

  26. Oh my goodness! Awesome article dude! Thanks, However
    I am encountering troubles with your RSS.
    I don’t understand the reason why I cannot join it.

    Is there anybody having identical RSS issues?

    Anyone who knows the answer can you kindly respond? Thanks!!

    Reply

  29. Thanks for a marvelous posting! I genuinely enjoyed reading
    it, you happen to be a great author.I will always bookmark your blog and will often come back
    at some point. I want to encourage that you continue your great job, have a nice weekend!

    Reply

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

    Reply

  34. My developer 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 various websites for about a year and am concerned
    about switching to another platform. I have heard great things about blogengine.net.
    Is there a way I can transfer all my wordpress posts into it?
    Any help would be really appreciated!

    Reply

  35. Good day! I could have sworn I’ve been to this site
    before but after checking through some of the post I realized it’s new
    to me. Anyhow, I’m definitely glad I found it and I’ll be book-marking and checking
    back often!

    Reply

  36. Heya just wanted to give you a brief heads up and let you know a few of the images aren’t
    loading properly. 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 results.

    Reply

  37. I am curious to find out what blog platform you happen to be working with?
    I’m experiencing some minor security issues with my latest website and I would like to
    find something more secure. Do you have any suggestions?

    Reply

  38. This design is spectacular! You most certainly know how to keep a reader amused.
    Between your wit and your videos, I was almost moved to start my own blog (well, almost…HaHa!) Great job.

    I really enjoyed what you had to say, and more than that, how you presented it.
    Too cool!

    Reply

  39. Hey! This post couldn’t be written any better!
    Reading this post reminds me of my good old room mate!
    He always kept talking about this. I will forward this article to
    him. Fairly certain he will have a good read.
    Thank you for sharing!

    Reply

  40. Wow! This blog looks exactly like my old one! It’s on a totally different subject but it has pretty much the same page layout
    and design. Outstanding choice of colors!

    Reply

  41. Have you ever considered creating an ebook or guest authoring on other blogs?

    I have a blog based on the same subjects you discuss and would love to have you
    share some stories/information. I know my subscribers would appreciate
    your work. If you’re even remotely interested, feel free to send me an e-mail.

    Reply

  42. I’m amazed, I must say. Rarely do I encounter a blog that’s both educative and engaging, and
    without a doubt, you’ve hit the nail on the head. The problem is something that
    not enough people are speaking intelligently about.
    I’m very happy I found this during my search for something concerning this.

    Reply

  43. I am not sure where you are getting your info,
    but good topic. I needs to spend some time learning much more or understanding more.
    Thanks for magnificent info I was looking for this information for my mission.

    Reply

  47. An impressive share! I have just forwarded this onto a coworker who has been conducting a little research on this.
    And he in fact ordered me dinner simply because I found it for him…
    lol. So let me reword this…. Thank YOU for
    the meal!! But yeah, thanks for spending the time to talk about this issue here on your site.

    Reply

  48. You really make it seem so easy along with your presentation however I in finding this matter to be really one thing which I think I might by no means understand.
    It kind of feels too complicated and extremely huge for me.
    I am looking ahead on your next put up, I will try to get
    the hang of it!

    Reply

  50. Hello There. I found your blog the usage of msn. This is a really neatly written article.
    I’ll be sure to bookmark it and return to read
    extra of your useful information. Thank you for the post.
    I will definitely return.

    Reply

  51. Hi to all, how is everything, I think every one is getting more from this
    web site, and your views are fastidious in support
    of new visitors.

    Reply

  52. Hello there, I believe your web site could be having internet browser compatibility problems.
    When I take a look at your blog in Safari, it looks fine however, when opening in Internet Explorer,
    it has some overlapping issues. I just wanted to provide you with a
    quick heads up! Other than that, great blog!

    Reply

  54. Hi there! This is my first visit to your blog!
    We are a team of volunteers and starting a
    new initiative in a community in the same niche.
    Your blog provided us useful information to work on. You have done a wonderful job!

    Reply

  55. It is appropriate time to make some plans for the future and it’s
    time to be happy. I’ve read this post and if
    I could I wish to suggest you some interesting things or
    tips. Maybe you could write next articles referring to
    this article. I want to read more things about it!

    Reply

  58. Thanks , I have recently been looking for information about this subject for a while
    and yours is the best I have found out so far. But, what in regards to the conclusion? Are you sure
    in regards to the supply?

    Reply

  69. Howdy, i read your blog occasionally and i own a similar one and i
    was just wondering if you get a lot of spam feedback?

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

    Reply

  76. Hi there, I discovered your web site by way of Google at the same time as looking for a
    comparable topic, your site came up, it seems great.
    I’ve bookmarked it in my google bookmarks.

    Hi there, simply changed into aware of your blog thru Google, and located that it’s really informative.
    I’m going to be careful for brussels. I will appreciate in the event you proceed this in future.
    Numerous other people shall be benefited out of your writing.
    Cheers!

    Reply

  87. Magnificent goods from you, man. I’ve understand
    your stuff previous to and you are just extremely excellent.
    I actually like what you’ve acquired here, really like what you’re
    saying and the way in which you say it. You make it enjoyable and you still take care of to keep it smart.
    I can’t wait to read much more from you. This is really a terrific website.

    Reply

  89. 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 experience so I
    wanted to get guidance from someone with experience.
    Any help would be greatly appreciated!

    Reply

  92. I used to be suggested this website by way of my cousin. I’m no longer positive whether this submit
    is written via him as no one else recognize such
    exact about my difficulty. You’re incredible! Thank you!

    Reply

  107. Awesome issues here. I am very satisfied to look your article.
    Thanks so much and I am taking a look forward to touch you.
    Will you kindly drop me a e-mail?

    Reply

  111. I do consider all of the ideas you’ve presented
    in your post. They’re very convincing and can certainly work.
    Nonetheless, the posts are too brief for
    newbies. May just you please lengthen them a bit from next time?
    Thanks for the post.

    Reply

  113. I take pleasure in, lead to I discovered just what I was having a look
    for. You have ended my 4 day long hunt! God Bless you
    man. Have a nice day. Bye

    Reply

  122. I’ve been absent for a while, but now I remember why I used to love this website. Thank you, I¦ll try and check back more frequently. How frequently you update your website?

    Reply

  125. Having read this I thought it was really informative.
    I appreciate you finding the time and energy to put this
    short article together. I once again find myself spending a lot of
    time both reading and posting comments. But so what,
    it was still worth it!

    Reply

  141. My spouse and I stumbled over here different web address
    and thought I might as well check things out. I like what I see
    so i am just following you. Look forward to going over your web page again.

    Reply

  143. I like the valuable information you provide in your articles.

    I’ll bookmark your blog and check again here frequently.

    I’m quite certain I will learn many new stuff right here!
    Best of luck for the next!

    Reply

  160. Hello there! Quick question that’s completely off topic.
    Do you know how to make your site mobile friendly?
    My blog 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. Cheers!

    Reply

  211. Valuable info. Lucky me I found your website unintentionally, and I am shocked
    why this coincidence did not happened earlier! I bookmarked it.

    Reply

  212. I was very pleased to find this web-site.I wanted to thanks for your time for this wonderful read!! I definitely enjoying every little bit of it and I have you bookmarked to check out new stuff you blog post.

    Reply

Leave a Reply

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