【BZOJ 2654】tree

链接

题目传送门: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;
}

23 thoughts to “【BZOJ 2654】tree”

  1. 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!

  2. 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!

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

  4. 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!

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

  6. 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!

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

  8. 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?

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

  10. Greetings! Very useful advice within this article!
    It’s the little changes which will make the most important changes.
    Thanks for sharing!

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

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

  13. 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!

Leave a Reply to Marisol Alpern Cancel reply

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