【BZOJ 2069】[POI2004] ZAW

Qizy 图论, 最短路, 解题报告

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2069
数据传送门：http://oi.cyo.ng/wp-content/uploads/2016/10/2069.rar

这题说两个做法：
1）最短路+奇怪的姿势，时间复杂度O(nlogn)
2）关键点间的最短路，时间复杂度O(nlog^2n)

先说第一种方式：
从1开始跑最短路，每个点记录最短路+次短路，保证路径上第二个点不同（1算第一个点）
然后O(n)扫描每一个点，使用最短路+次短路更新答案即可
这种方法虽然时间复杂度较优，但不是很通用

接下来我们说一说关键点间的最短路：
考虑将答案路径与1相连的两条边删掉
路径变为与1相连的点间的最短路径
于是将与1相邻的点设为关键点，跑关键点间的最短路即可

接下来说一说怎么跑关键点间的最短路：
考虑拆二进制，枚举二进制的每一位。
根据这一位是否为1，将关键点分为两个点集
然后一个连超级源，另一个连超级汇即可
时间复杂度O(nlog^2(n))
其实这才是这篇题解的重点

这里是二进制拆分+Dijkatra的代码，请随意食用~

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

const int N = 50000+9;
const int M = 300000+9;
const int INF = 1e9;

int head[N],dis[N],t1[N],t2[N],t3[N],head_tmp[N],tot,TT,S,T,vout=INF,n,m,nxt[M],to[M],cost[M];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > que; bool 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 void Add_Edge(int u, int v, int c1, int c2) {
	to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; cost[TT] = c1;
	to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; cost[TT] = c2;
}

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

int main(){
	n = read(); m = read();
	for (int i=1,a,b,c,d;i<=m;i++) {
		a = read(); b = read();
		c = read(); d = read();
		Add_Edge(a, b, c, d);
		
		if (a == 1) {
			t1[++tot] = b;
			t2[tot] = c;	
			t3[tot] = d;
		} else if (b == 1) {
			t1[++tot] = a;
			t2[tot] = d;
			t3[tot] = c;
		}
	}
	
	S = N - 1; T = N - 2;
	int w = 0, TMP = n, ori = TT;
	while (TMP) w++, TMP >>= 1;
	memcpy(head_tmp,head,sizeof(head));
	
	for (int k=0,cur=1;k<=w;k++,cur<<=1) {
		TT = ori;
		memcpy(head,head_tmp,sizeof(head));
		
		for (int i=1;i<=tot;i++) {
			if (t1[i]&cur) Add_Edge(S,t1[i],t2[i],INF);
			else Add_Edge(t1[i],T,t3[i],INF);
		} 
		vout = min(Dijkstra(), vout);
		
		TT = ori;
		memcpy(head,head_tmp,sizeof(head));
		
		for (int i=1;i<=tot;i++) {
			if (t1[i]&cur) Add_Edge(t1[i],T,t3[i],INF);
			else Add_Edge(S,t1[i],t2[i],INF);
		} 
		vout = min(Dijkstra(), vout);
	}
	printf("%d\n",vout);
	return 0;
}

76 thoughts to “【BZOJ 2069】[POI2004] ZAW”

  3. I have been surfing online more than three hours lately,
    yet I by no means found any interesting article like yours.
    It is beautiful worth enough for me. In my view, if all web owners and bloggers made excellent content as you probably did,
    the net shall be much more helpful than ever before.

    Reply

  8. I’m really loving the theme/design of your web site. Do
    you ever run into any browser compatibility issues? A couple of my blog audience have complained about my site not working correctly in Explorer
    but looks great in Chrome. Do you have any tips to
    help fix this problem?

    Reply

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

    Reply

  10. Link exchange is nothing else except it is just placing
    the other person’s webpage link on your page at appropriate place and
    other person will also do same in favor of you.

    Reply

  15. I’ve been surfing online more than 3 hours nowadays, but I never discovered any interesting article like
    yours. It’s lovely value enough for me. In my view, if
    all webmasters and bloggers made excellent content material as you probably did,
    the web can be much more helpful than ever before.

    Reply

  17. Having read this I believed it was really
    enlightening. I appreciate you finding the time and effort to
    put this information together. I once again find myself personally spending a lot
    of time both reading and leaving comments. But so what, it was still worthwhile!

    Reply

  19. I believe this is among the most important info for me.
    And i am glad reading your article. But wanna commentary on few common issues,
    The site style is ideal, the articles is in reality nice
    : D. Just right job, cheers natalielise pof

    Reply

  21. I have been surfing 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 a lot more useful than ever before.

    Reply

  25. 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 quick. I’m thinking about making my own but I’m not sure where to begin. Do you have any tips
    or suggestions? Thank you

    Reply

  28. Attractive section of content. I just stumbled upon your weblog
    and in accession capital to assert that I get in fact enjoyed account your blog posts.
    Anyway I’ll be subscribing to your augment and even I achievement you access consistently quickly.

    Reply

  31. I feel that is one of the so much significant info
    for me. And i am glad reading your article.
    However want to statement on some general things, The web site style is great, the articles is in point of fact great : D.

    Excellent process, cheers

    Reply

  33. great post, very informative. I’m wondering why the other specialists of this sector don’t understand this.
    You should continue your writing. I’m sure, you have
    a huge readers’ base already!

    Reply

  34. I don’t even know how I ended up here, but I thought this
    post was good. I don’t know who you are but certainly you are going to a famous blogger if you
    are not already 😉 Cheers!

    Reply

  37. Excellent blog here! Also your website loads up fast!

    What web host are you using? Can I get your affiliate link to
    your host? I wish my web site loaded up as quickly as yours lol

    Reply

  39. I do believe all of the concepts you’ve offered in your post.
    They’re really convincing and can certainly work. Nonetheless, the posts are very short
    for beginners. Could you please extend them a little from
    next time? Thank you for the post.

    Reply

  41. I do not even know how I ended up here, but I thought this
    post was great. I do not know who you are but definitely you are
    going to a famous blogger if you aren’t already 😉 Cheers!

    Reply

  42. I am really loving the theme/design of your weblog.
    Do you ever run into any internet browser compatibility problems?
    A few of my blog readers have complained about my website not
    working correctly in Explorer but looks great in Opera. Do you have any
    tips to help fix this problem?

    Reply

  44. Pretty component of content. I just stumbled upon your web site and in accession capital to say that I get in fact
    loved account your blog posts. Anyway I will be subscribing in your augment and
    even I success you get right of entry to persistently quickly.

    Reply

  47. Its such as you read my thoughts! You seem to understand a lot approximately this, such as
    you wrote the e-book in it or something. I think that you can do
    with a few percent to pressure the message home a
    bit, however instead of that, this is great blog.
    A great read. I’ll certainly be back.

    Reply

  52. Woah! I’m really enjoying the template/theme of this website.
    It’s simple, yet effective. A lot of times it’s challenging
    to get that “perfect balance” between user friendliness
    and visual appeal. I must say that you’ve done a fantastic job with
    this. Additionally, the blog loads super fast for me on Opera.
    Exceptional Blog!

    Reply

  53. Write more, thats all I have to say. Literally, it seems as though you relied on the video
    to make your point. You definitely know what youre talking
    about, why waste your intelligence on just posting videos to
    your site when you could be giving us something informative to read?

    Reply

  56. My developer is trying to persuade 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 WordPress on a number of websites for about a year
    and am concerned 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 kind of help would be really appreciated!

    Reply

  57. I am not sure the place you’re getting your information, but good
    topic. I must spend some time finding out more or
    understanding more. Thank you for excellent info
    I used to be in search of this info for my mission.

    Reply

  58. I just like the valuable information you supply for your articles.
    I’ll bookmark your weblog and check again here frequently.

    I am fairly sure I’ll be informed lots of new stuff proper right here!
    Best of luck for the next!

    Reply

  59. Hi there! I know this is somewhat off topic but I was wondering if you knew where I could
    locate a captcha plugin for my comment form? I’m using the same blog platform as yours and I’m having trouble finding
    one? Thanks a lot!

    Reply

  60. Usually I do not read article on blogs, however I would like to say that this write-up very compelled me to check out and do so!
    Your writing style has been surprised me. Thank you, quite
    nice article.

    Reply

  62. My partner and I absolutely love your blog and find many of your post’s to be what
    precisely I’m looking for. Does one offer guest writers to write content available for you?
    I wouldn’t mind composing a post or elaborating on most of the subjects you write with regards to here.
    Again, awesome weblog!

    Reply

  65. I like the valuable info you provide in your articles.
    I will bookmark your weblog and check again here regularly.
    I am quite sure I’ll learn lots of new stuff right here!
    Good luck for the next!

    Reply

  71. I do not even understand how I ended up right here, however I believed this publish was once good.
    I don’t know who you’re however certainly you’re going
    to a famous blogger for those who are not already.

    Cheers!

    Reply

  72. Magnificent website. Plenty of helpful information here.
    I am sending it to some friends ans additionally sharing in delicious.
    And certainly, thank you on your effort!

    Reply

Leave a Reply

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