链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2654
神犇题解:http://blog.csdn.net/PoPoQQQ/article/details/47980565
题解
感觉这个题很好玩的样子!
考虑给每一个白边加上一个固定的权值
那么使用白边的数量可以用这个权值来调整
唯一需要注意的就是,这种变化可能不是线性的
也就是说可能会有断层的情况,需要特殊处理一下
值得注意的是,这种方法具有较高的可移植性:
在某一套小火车的模拟题中,一道很恶心的DP也可以用此方法来解决
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 100000+9; struct Edge{int u,v,val,col;}e[N]; int n,m,STA,fa[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 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; } bool cmp_mx(const Edge &A, const Edge &B) {return A.val < B.val || (A.val == B.val && A.col > B.col);} bool cmp_mn(const Edge &A, const Edge &B) {return A.val < B.val || (A.val == B.val && A.col < B.col);} inline bool judge(int delta) { int cnt = 0; sort(e+1, e+1+m, cmp_mx); for (int i=1;i<=n;i++) fa[i] = i; for (int i=1;i<=m;i++) { if (find(e[i].u) != find(e[i].v)) { fa[find(e[i].u)] = find(e[i].v); cnt += e[i].col; } } if (cnt < STA) return 1; int cost = 0; cnt = 0; sort(e+1, e+1+m, cmp_mn); for (int i=1;i<=n;i++) fa[i] = i; for (int i=1;i<=m;i++) { if (find(e[i].u) != find(e[i].v)) { fa[fa[e[i].u]] = fa[e[i].v]; cnt += e[i].col; cost += e[i].val; } } if (cnt > STA) return 0; else { printf("%d\n",cost-STA*delta); exit(0); } } int main(){ n = read(); m = read(); STA = read(); for (int i=1;i<=m;i++) { e[i].u = read() + 1; e[i].v = read() + 1; e[i].val = read(); e[i].col = read() ^ 1; } int l=-100,r=100,mid; while (l <= r) { mid = l + r >> 1; for (int i=1;i<=m;i++) if (e[i].col) e[i].val += mid; if (judge(mid)) r = mid - 1; else l = mid + 1; for (int i=1;i<=m;i++) if (e[i].col) e[i].val -= mid; } return 0; }
I’m really enjoying the design and layout of your site.
It’s a very easy on the eyes which makes it much more
pleasant for me to come here and visit more often. Did you hire out
a developer to create your theme? Superb work!
You made some really good points there. I looked on the net for more information about the issue and found most people will go along with your
views on this site.
First off I want to say excellent blog! I had a quick question which
I’d like to ask if you don’t mind. I was curious to find out how you center yourself and clear your mind prior to writing.
I have had trouble clearing my thoughts in getting my ideas out there.
I do enjoy writing however it just seems like the first 10 to 15 minutes are lost just trying to figure out how to begin. Any ideas or hints?
Many thanks!
That is very attention-grabbing, You are a
very skilled blogger. I have joined your feed and sit up for in quest of more of your fantastic post.
Also, I’ve shared your website in my social networks
Hi would you mind stating which blog platform you’re working with?
I’m looking to start my own blog soon but I’m having a tough time deciding between BlogEngine/Wordpress/B2evolution and Drupal.
The reason I ask is because your design and style seems different then most blogs and I’m looking for something unique.
P.S My apologies for being off-topic but I had to ask!
Howdy would you mind letting me know which webhost you’re using?
I’ve loaded your blog in 3 different browsers and I must
say this blog loads a lot quicker then most. Can you suggest a
good hosting provider at a reasonable price? Cheers, I appreciate it!
Hello everyone, it’s my first pay a visit at this web page, and piece of writing is actually
fruitful for me, keep up posting these articles.
What’s up to every , since I am in fact keen of reading this
web site’s post to be updated on a regular basis. It carries fastidious stuff.
I used to be able to find good information from your blog posts.
Wow! This blog looks exactly like my old one! It’s on a completely different subject but it has pretty much the same page layout and design. Excellent choice of colors!
This website was… how do I say it? Relevant!! Finally I have found something which helped me.
Thanks!
What’s Going down i’m new to this, I stumbled upon this I’ve found
It absolutely helpful and it has helped me
out loads. I’m hoping to contribute & aid other users like its helped me.
Great job.
I was recommended this web site by my cousin.
I am not sure whether this post is written by him as nobody else know
such detailed about my difficulty. You are wonderful!
Thanks!
Keep on working, great job!
I was wondering if you ever thought of changing the structure of your website?
Its very well written; I love what youve got to say.
But maybe you could a little more in the way
of content so people could connect with it better. Youve got an awful lot of text
for only having 1 or two pictures. Maybe you could space it out better?
Hi to every body, it’s my first go to see of this webpage; this blog consists of awesome and
actually fine material in support of readers.
Amazing! Its really awesome post, I have got much clear idea about from
this piece of writing.
Hurrah! At last I got a website from where I
be capable of truly take valuable information regarding my
study and knowledge.
Greetings! Very useful advice within this article!
It’s the little changes which will make the most important changes.
Thanks for sharing!
Hey There. I discovered your blog the usage of msn.
This is a really neatly written article. I’ll make sure to bookmark it and come back to read more of your helpful info.
Thanks for the post. I’ll definitely comeback.
Yes! Finally someone writes about sling tv.
I am really impressed along with your writing talents and also with the structure
in your blog. Is this a paid subject or did you modify it yourself?
Anyway stay up the excellent quality writing, it is uncommon to peer a great blog like
this one nowadays..
Thanks a bunch for sharing this with all of us you actually know what you are speaking approximately! Bookmarked. Please also visit my web site =). We may have a hyperlink exchange agreement among us!