蒟蒻求助qwq……

回复帖子

@Irressey 2018-10-20 08:41 回复

感觉思路应该没有问题 然而全WA了qwq

代码

#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#define ll long long
#define maxn 50005
using namespace std;
inline ll read(){
    ll d=0;char ch=getchar();while(!isdigit(ch))ch=getchar();
    while(isdigit(ch)){d=d*10+ch-48;ch=getchar();}return d;
}
ll v,e,n;
ll ls=-1e3,rs=1e3,mid;
struct node{
    int s,t,col;
    ll w;
    bool operator<(const node &x)const{
        if(w+(col?0:mid)==x.w+(x.col?0:mid))return col<x.col;
        return w+(col?0:mid)<x.w+(x.col?0:mid);
    }
}c[maxn<<1];
int f[maxn];
int getf(int x){
    return x==f[x]?x:f[x]=getf(f[x]);
}
bool merge(int x,int y){
    int fx=getf(x),fy=getf(y);
    if(fx==fy)return false;
    f[fx]=fy;
    return true;
}
int check(int x){
    sort(c+1,c+e+1);
    for(int i=1;i<=v;++i)
        f[i]=i;
    int cnt=n,slt=0;
    for(int i=1;i<=e;++i){
        if(merge(c[i].s,c[i].t)){
            --cnt;
            if(!c[i].col)++slt;
            if(cnt==1)return slt;
        }
    }
    return slt;
}
int main(){
    v=read(),e=read(),n=read();
    for(int i=1;i<=e;++i){
        c[i].s=read()+1,c[i].t=read()+1,c[i].w=read(),c[i].col=read();
    }
    while(ls<rs){
        mid=(ls+rs+1)>>1;
        int cnt=check(mid);
        if(cnt>=n)ls=mid;
        else rs=mid-1;
    }
    for(int i=1;i<=v;++i)
        f[i]=i;
    ll cnt=n,slt=0;
    for(int i=1;i<=e;++i){
        if(merge(c[i].s,c[i].t)){
            --cnt;
            slt+=c[i].w;
            if(cnt==1)break;
        }
    }
    printf("%lld",slt);
    return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。