相关链接
题目传送门:http://cf16-final.contest.atcoder.jp/tasks/codefestival_2016_final_g
官方题解:http://oi.cyo.ng/wp-content/uploads/2017/01/atcoder_codefestival_2016_final_g.pdf
解题报告
先来看任意一个连边操作:
考虑正常的最小生成树算法,如果用到了价值为 $ c+1$ 的边,那么价值为 $ c$ 的边一定已经考虑过了
于是我们就可以把图等价地变换为下面这个样子:
这样的话,我们可以把价值为 $ c$ 地那一类边拿出来单独考虑
余下的边搞一个堆,连一圈
这样的话,我们的图就改造成了这个样子:
此时我们的边就只剩 $ N+Q$ 条了,直接跑最小生成树算法就可以啦!
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 400000+9; struct Edge{int u,v,w;}e[N]; struct Operation{int p,c;}op[N]; priority_queue<Operation> que; int n,m,tot,vis[N],fa[N]; LL vout; inline bool operator < (const Edge &A, const Edge &B) {return A.w < B.w;} inline bool operator < (const Operation &A, const Operation &B) {return A.c > B.c;} 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 int find(int w) { int f = fa[w], tmp; while (f != fa[f]) f = fa[f]; while (w != f) tmp = fa[w], fa[w] = f, w = tmp; return f; } int main() { n = read(); m = read(); for (int i=1,a,b,c;i<=m;i++) { a = read(); b = read(); c = read(); e[++tot] = (Edge){a, b, c}; que.push((Operation){a, c+1}); que.push((Operation){b, c+2}); } while (!que.empty()) { Operation w = que.top(); que.pop(); if (!vis[w.p]) { vis[w.p] = 1; e[++tot] = (Edge){w.p, (w.p+1)%n, w.c}; que.push((Operation){(w.p+1)%n, w.c+2}); } } sort(e+1, e+1+tot); for (int i=0;i<=n;i++) fa[i] = i; for (int i=1;i<=tot;i++) { if (find(e[i].u) != find(e[i].v)) { fa[fa[e[i].u]] = fa[e[i].v]; vout += e[i].w; } } printf("%lld\n",vout); return 0; }
I am so grateful for your article.Really thank you! Will read on…
I truly appreciate this article.Thanks Again. Keep writing.
Really appreciate you sharing this article.Really thank you! Awesome.
I really liked your blog.Really looking forward to read more. Really Great.
Muchos Gracias for your article post. Cool.
Very informative article post.Really thank you! Awesome.
I cannot thank you enough for the blog article.Thanks Again. Will read on…
I really liked your post.Really thank you! Want more.
Major thankies for the blog article.Really looking forward to read more. Fantastic.
Im grateful for the article.Much thanks again. Will read on…
Really appreciate you sharing this blog.Much thanks again. Will read on…
Very neat blog post.Thanks Again. Much obliged.
Im grateful for the blog post.Much thanks again. Will read on…
I loved your blog article.Really looking forward to read more. Great.
Thanks for the blog post.Really looking forward to read more.
Thanks a lot for the blog post.Much thanks again. Really Cool.
Major thanks for the post.Really looking forward to read more. Really Great.
Major thankies for the post.Thanks Again. Cool.
I appreciate you sharing this post.Thanks Again.
Great blog article.Much thanks again. Much obliged.
wow, awesome blog.Really looking forward to read more. Much obliged.
I value the blog article.Thanks Again. Will read on…
Major thankies for the blog.Really thank you! Cool.
Very neat article post.Really thank you!
Enjoyed every bit of your blog. Great.
Appreciate you sharing, great blog.Thanks Again. Really Great.
Hey, thanks for the blog.Thanks Again. Really Cool.
Muchos Gracias for your article.Much thanks again. Will read on…
Major thankies for the blog.Really thank you! Fantastic.
Really informative post.Much thanks again.
Very neat blog post.Really looking forward to read more. Really Cool.
Really appreciate you sharing this blog.Thanks Again. Really Cool.
Really enjoyed this blog article. Great.
Awesome post.
Appreciate you sharing, great article post.Really thank you! Fantastic.
Im thankful for the article post.Much thanks again. Want more.
I appreciate you sharing this blog article.Really thank you! Great.
I appreciate you sharing this post.Really thank you! Keep writing.
Thanks again for the post.Really thank you! Cool.
Thank you ever so for you blog article.Really thank you! Awesome.
A big thank you for your blog article.Much thanks again. Great.
A big thank you for your post.Really looking forward to read more. Awesome.
Im thankful for the article.
Thanks for sharing, this is a fantastic blog article.Thanks Again. Cool.
I really enjoy the blog article.Thanks Again. Great.
Thanks again for the article.Really looking forward to read more. Keep writing.
I loved your post.Much thanks again. Fantastic.
I loved your article.Really thank you!
Major thanks for the blog post. Really Great.
I appreciate you sharing this blog.Really thank you! Much obliged.
I am always browsing online for tips that can help me. Thx!
Very neat article post.Really looking forward to read more. Keep writing.
Thank you for your article.Much thanks again. Really Cool.
Say, you got a nice post.Really thank you! Really Great.
Very informative article post.Much thanks again. Really Great.
Really informative blog.Really looking forward to read more. Much obliged.
A big thank you for your blog.Thanks Again. Will read on…
Major thanks for the blog post.Much thanks again. Great.
A big thank you for your blog post.Really looking forward to read more. Awesome.
I really liked your blog post.Thanks Again. Fantastic.
I really like and appreciate your blog post.Really thank you! Fantastic.
I truly appreciate this blog.Thanks Again. Keep writing.
Thank you for your article post.Really looking forward to read more. Really Great.
Thanks again for the blog. Great.
I cannot thank you enough for the article post.Really looking forward to read more. Really Great.
Awesome blog.Thanks Again. Really Cool.
Say, you got a nice post.Really looking forward to read more. Awesome.
Very good article post.Thanks Again. Want more.
This is one awesome blog.Thanks Again.
Very good blog.Thanks Again. Fantastic.
Im grateful for the blog post.Really thank you! Really Cool.
I am so grateful for your article.Really thank you! Want more.
I think this is a real great article post. Want more.
I loved your post.Much thanks again. Fantastic.
Really informative article post.Really thank you! Much obliged.
Major thanks for the post. Awesome.
Really enjoyed this blog post.Thanks Again. Much obliged.
I am so grateful for your blog. Cool.
I value the blog article.Really thank you! Much obliged.
Im grateful for the article post.Thanks Again. Keep writing.
Thanks for the article post.Thanks Again.
Looking forward to reading more. Great blog article.Really thank you!
Say, you got a nice article. Cool.
Thanks-a-mundo for the article post.Much thanks again.
Great, thanks for sharing this article post.Really looking forward to read more. Awesome.
Muchos Gracias for your blog post.Really thank you! Great.
Really informative blog article.Really thank you! Will read on…
Really enjoyed this article.Really looking forward to read more. Want more.
I appreciate you sharing this blog article.Really looking forward to read more. Really Cool.
This is one awesome blog.Really thank you! Want more.
This is one awesome article post.Really thank you! Much obliged.
Thanks-a-mundo for the article.Really thank you! Much obliged.
Thank you ever so for you article post.Much thanks again. Want more.
I appreciate you sharing this article.Really looking forward to read more. Great.
Enjoyed every bit of your post.Thanks Again.
Thanks-a-mundo for the article post.Thanks Again. Will read on…
I truly appreciate this blog post.Thanks Again. Keep writing.
Great blog post. Awesome.
I loved your post.Much thanks again. Cool.
Thanks for sharing, this is a fantastic article post.Really looking forward to read more. Much obliged.
Thanks so much for the blog article.Really thank you! Keep writing.
Thank you for your post.Really thank you! Really Cool.
Major thankies for the blog post.Much thanks again. Really Great.
I appreciate you sharing this blog.Really thank you! Want more.
Thank you ever so for you blog article.Really looking forward to read more. Awesome.
Thanks for the blog.Really thank you! Really Great.
Wow, great blog post.Much thanks again. Fantastic.
Say, you got a nice blog article. Fantastic.
Muchos Gracias for your blog post.
Great article post.Much thanks again. Awesome.
I appreciate you sharing this blog.Thanks Again. Will read on…
Fantastic article post.Much thanks again. Great.
Say, you got a nice blog post.Much thanks again. Cool.
Im thankful for the post.Really thank you! Cool.
I think this is a real great blog. Fantastic.
I loved your article post.Thanks Again. Really Great.
Thanks for sharing, this is a fantastic post.Really thank you! Much obliged.
Enjoyed every bit of your blog.Really thank you! Really Cool.
Major thankies for the blog article.Really looking forward to read more. Much obliged.
Hey, thanks for the blog article.Thanks Again. Great.
Thanks a lot for the blog.Much thanks again. Fantastic.
Thanks a lot for the post.Really thank you! Keep writing.
Awesome post.Thanks Again. Really Cool.
Major thanks for the article.Really looking forward to read more. Cool.
Very neat blog article. Will read on…
Appreciate you sharing, great article post.Much thanks again. Keep writing.
Fantastic blog article.Really thank you! Want more.
I cannot thank you enough for the blog post.Really thank you! Want more.
I really like and appreciate your post.Thanks Again. Much obliged.
I appreciate you sharing this blog post.Much thanks again. Really Great.
Wow, great blog.Thanks Again. Will read on…
Awesome post.Thanks Again. Really Great.
Thanks for sharing, this is a fantastic blog article.Much thanks again. Fantastic.
Some really marvelous work on behalf of the owner of this web site, perfectly great written content.
Hey, thanks for the post.Thanks Again. Really Cool.
Thanks for the blog post.Really looking forward to read more. Much obliged.
Thank you ever so for you post. Keep writing.
Fantastic blog.Much thanks again. Fantastic.
Thanks again for the blog post.Really looking forward to read more. Much obliged.
Thank you ever so for you blog article.Much thanks again. Really Great.
wow, awesome blog post.Really thank you! Keep writing.
Really informative article post.Much thanks again. Cool.
A round of applause for your article post.Really looking forward to read more. Want more.
I am so grateful for your article.Much thanks again. Great.
Major thanks for the blog. Awesome.
wow, awesome blog article.Thanks Again. Awesome.
I really like and appreciate your post.Thanks Again. Really Cool.
Muchos Gracias for your blog post. Awesome.
Thanks-a-mundo for the blog post. Great.
A round of applause for your blog.Much thanks again. Keep writing.
wow, awesome blog article.Really looking forward to read more. Much obliged.
I truly appreciate this blog.Really looking forward to read more. Awesome.
Major thanks for the post. Want more.
Thanks-a-mundo for the blog.Really thank you! Want more.
Say, you got a nice blog article. Keep writing.
Thanks again for the blog article.Really thank you! Much obliged.
Very good article post.Much thanks again. Cool.
Major thanks for the blog.Really looking forward to read more. Keep writing.
I truly appreciate this blog article.Thanks Again. Want more.
Say, you got a nice article. Keep writing.
A round of applause for your blog article.Really thank you! Much obliged.
Thanks a lot for the blog article. Awesome.
I think this is a real great blog post.Really thank you! Cool.
Awesome blog article. Great.
Im thankful for the article post.Much thanks again. Want more.
Fantastic article post.Really thank you! Much obliged.
Great article post.Really thank you! Cool.
Appreciate you sharing, great blog article.Really looking forward to read more. Fantastic.
I truly appreciate this blog.Much thanks again.
Great article post.Really thank you! Awesome.
Major thankies for the article post.Thanks Again. Want more.
Very good post.Thanks Again. Great.
Say, you got a nice post.Really thank you! Much obliged.
I really liked your blog article. Really Cool.
A round of applause for your article.Really thank you! Keep writing.