BZOJ2654 tree

最小生成树

思路:给每一条白边加上一个权值,后做最小生成树,由于最小生成树的定义,白边的值越小,则树中白边数越多,具有单调性,所以可以二分。二分这个权值,使得白边的个数恰好为所需个数。

这题的思路看完题解后还是捋的清的,但是自己敲代码的时候按照自己写的却不能A掉这道题,把这错误记录下来。

AC代码

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

const int N=1e5+10;

int n,m,s,ans,cnt;
struct node{
    int u,v,c,w,id;
}a[N];
int w[N];
int f[N];
bool cmp(node a,node b){
    if(a.w==b.w) return a.c<b.c;
    return a.w<b.w;
}
int find(int x){
    return f[x]==x?x:f[x]=find(f[x]);
}

bool check(int x){
    ans=0;
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<=m;i++){
        if(!a[i].c) a[i].w=w[a[i].id]+x;
    }
    cnt=0;
    sort(a+1,a+1+m,cmp);
    for(int i=1;i<=m;i++){
        int u=a[i].u,v=a[i].v;
        if(find(u)!=find(v)){
            f[find(u)]=find(v);
            cnt+=(a[i].c==0);
            ans+=a[i].w;
        }
    }
    if(cnt>=s) return 1;
    return 0;
}
int qu[N];
signed  main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    //freopen("2.in","r",stdin);
    // freopen("3.out","w",stdout);
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        int x,y,c;
        cin>>x>>y>>w[i]>>c;
        x++,y++;
        a[i]={x,y,c,w[i],i};
    }
    int l=-100,r=100;
    while(l<r){
        int mid=(l+r+1)>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    check(l);
    cout<<ans-s*l<<'\n';
}

错误代码

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

const int N=1e5+10;

int n,m,s,ans,cnt;
struct node{
    int u,v,c,w,id;
}a[N];
int w[N];
int f[N];
bool cmp(node a,node b){
    if(a.w==b.w) return a.c<b.c;
    return a.w<b.w;
}
int find(int x){
    return f[x]==x?x:f[x]=find(f[x]);
}

bool check(int x){
    ans=0;
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<=m;i++){
        if(!a[i].c) a[i].w=w[a[i].id]+x;
    }
    cnt=0;
    sort(a+1,a+1+m,cmp);
    for(int i=1;i<=m;i++){
        int u=a[i].u,v=a[i].v;
        if(find(u)!=find(v)){
            f[find(u)]=find(v);
            cnt+=(a[i].c==0);
            ans+=w[a[i].id];
        }
    }
    if(cnt>=s) return 1;
    return 0;
}
int qu[N];
signed  main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    //freopen("2.in","r",stdin);
    // freopen("3.out","w",stdout);
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        int x,y,c;
        cin>>x>>y>>w[i]>>c;
        x++,y++;
        a[i]={x,y,c,w[i],i};
    }
    int l=-100,r=100;
    while(l<r){
        int mid=(l+r+1)>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    check(l);
    cout<<ans<<'\n';
}

刚开始百思不得其解,为什么只能写 “` ans-s*l “` 的版本,后来仔细想了想,这题的边的大小范围太小,导致会有许多边权相等的边,因为在白边和黑边边权相同的情况下先处理了白边,就使得白边的选择数量可能过多或过少(起冲突),二分出来的 $ l $ 只能是一个恰好大一点的值,不能保证在check里的就是最终答案,总而言之,因为边权的范围太小了所以会有冲突,所以只能写减去的版本。(也许不是很好理解)

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇