求助wa3个点

回复帖子

@Twinkle_M 2019-02-27 21:02 回复
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
struct node {
    int u;
    int v;
    int w;
    int col;
} e[5000055],a[5000055];
int n,m,k;
bool cmp(const node&x,const node&y)
{
    return x.w<y.w;
}
int l,r;
int fa[5000005];
int find(int x)
{
    if(fa[x]==x)
    return x;
    return fa[x]=find(fa[x]);
}
int minn;
bool check(int x)
{
    int need=0;
    int ans=0;
    int num=0;
    for(int i=1;i<=m;i++)
    {
        a[i]=e[i];
        if(a[i].col==0)
        a[i].w+=x;
    }
    sort(a+1,a+1+m,cmp);
    for(int i=1;i<=n;i++)
    fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        int u=find(a[i].u);
        int v=find(a[i].v);
        if(u==v)
        continue;
        num++;
        fa[u]=v;
        ans+=a[i].w;
        if(a[i].col==0)
        need++;
        if(n-1==num)
        break;
    }
    minn=ans;
    if(need>=k)
    return 1;
    return 0;
}
int main() {
    cin>>n>>m>>k;
    for(int i=1; i<=m; i++) {
        int x,y,z,d;
        scanf("%d%d%d%d",&x,&y,&z,&d);
        e[i].u=x+1;
        e[i].v=y+1;
        e[i].w=z;
        e[i].col=d;
    }
    l=-100;
    r=100;
    int wzx;
    while(l<=r) {
        int mid=(l+r)>>1;
        if(check(mid))
            l=mid+1,wzx=mid;
        else
            r=mid-1;
    }
    check(wzx);
//  cout<<ans<<" "<<minn<<endl;
    cout<<minn-k*wzx<<endl;
    return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



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