相关链接
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4886
官方题解：http://oi.cyo.ng/wp-content/uploads/2017/05/ludsy_may_contest_solution.pdf
解题报告
我们把权值看做点，矩形看作边
不难发现一个大小为$n$连通块如果是树，那么最多选$n-1$个点
否则可以选完$n$个点
所以用并查集维护一下连通性之后
直接贪心即可
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 500009;
int n,tot,u[N],v[N],fa[N],val[N],cir[N],sz[N];
LL ans;
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;
}
int find(int x) {
return x == fa[x]? x: fa[x] = find(fa[x]);
}
int main() {
n = read();
for (int i=1;i<=n;i++) {
u[i] = val[++tot] = read();
v[i] = val[++tot] = read();
ans += u[i];
ans += v[i];
}
sort(val+1, val+1+tot);
tot = unique(val+1, val+1+tot) - val - 1;
for (int i=1;i<=tot;i++) {
fa[i] = i;
sz[i] = 1;
}
for (int i=1;i<=n;i++) {
int x = lower_bound(val+1, val+1+tot, u[i]) - val;
int y = lower_bound(val+1, val+1+tot, v[i]) - val;
if (find(x) != find(y)) {
sz[fa[y]] += sz[fa[x]];
if (cir[fa[x]]) {
cir[fa[y]] = 1;
}
fa[fa[x]] = fa[y];
} else {
cir[fa[x]] = 1;
}
}
for (int i=1;i<=tot;i++) {
if (find(i) == i) {
sz[i] -= (cir[i] ^ 1);
}
}
for (int i=1,w=1;i<=n;i++,w++) {
while (sz[find(w)] == 0) ++w;
ans -= val[w];
sz[fa[w]]--;
}
printf("%lld\n",ans);
return 0;
}
Hi would you mind stating which blog platform you’re working with?
I’m planning to start my own blog soon but I’m having
a tough time selecting between BlogEngine/Wordpress/B2evolution and
Drupal. The reason I ask is because your layout seems different then most blogs and I’m looking for something unique.
P.S Sorry for getting off-topic but I had to ask!
Keep on writing, great job!
Hey there! I know this is kinda 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 problems finding one? Thanks a lot!
Very nice post. I just stumbled upon your blog and wanted to say that
I have truly enjoyed browsing your blog posts. After all I’ll be subscribing to your rss feed
and I hope you write again very soon!
Thanks very interesting blog!
always i used to read smaller articles which also clear
their motive, and that is also happening with this article which I am reading now.
Nice weblog right here! Also your website lots up fast!
What host are you using? Can I get your associate
link for your host? I want my website loaded up
as quickly as yours lol
Everyone loves what you guys are usually up too. This type of clever work and exposure!
Keep up the very good works guys I’ve added you guys
to blogroll.
Great work! That is the type of information that are meant to
be shared across the web. Shame on the search engines for not positioning this publish higher!
Come on over and seek advice from my web site . Thanks =)
I’m not sure where you are getting your info,
but good topic. I needs to spend some time learning more or understanding more.
Thanks for great info I was looking for this information for my mission.
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.
I am not really wonderful with English but I get hold this real easygoing to read .
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 entirely off topic but I had to
tell someone!
Hello there, I discovered your website via Google even as looking for a related topic, your site got here up,
it seems to be great. I have bookmarked it in my google bookmarks.
Hi there, simply was aware of your weblog thru Google,
and found that it is really informative. I’m going to watch out for brussels.
I will be grateful should you continue this in future. Numerous folks can be benefited out of your writing.
Cheers!
I like the valuable information you provide in your articles.
I will bookmark your blog and check again here frequently.
I am quite certain I’ll learn many new stuff right here!
Good luck for the next!
Great post.
Good respond in return of this question with firm
arguments and telling the whole thing about that.
Greetings from Colorado! I’m bored at work so I decided to check out your site
on my iphone during lunch break. I really like the info you provide here and can’t wait to take
a look when I get home. I’m surprised at how fast your blog loaded on my
mobile .. I’m not even using WIFI, just 3G .. Anyhow, superb site!
This post will assist the internet visitors for creating new web site or even a weblog from start
to end.
Good post. I learn something new and challenging on blogs I stumbleupon every day.
It’s always exciting to read through content from other authors and use a little something from their
sites.
Today, while I was at work, my sister stole my iPad and tested to see if
it can survive a thirty foot drop, just so she can be a youtube sensation. My iPad is now destroyed and she
has 83 views. I know this is entirely off topic but I had
to share it with someone!
I every time used to study piece of writing in news papers but now as I
am a user of web so from now I am using net for posts,
thanks to web.
Piece of writing writing is also a excitement, if you know after that you can write if not it is difficult to write.
Hi 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 browsers and both show the same results.
I just couldn’t leave your web site before suggesting that I extremely loved the usual information an individual supply on your guests? Is gonna be again frequently to check out new posts
Great blog article. Want more.