萌新真的刚学OI,请教大佬一个弱智的question!!!

回复帖子

@Dickk 2019-04-12 20:23 回复
#include<bits/stdc++.h>
using namespace std;
int n,m,need,ans,anss;
int fa[100005];
struct arr{
    int x,y,z,col;
}a[100005],b[100005];
int getfa(int x){return fa[x]==x?x:fa[x]=getfa(fa[x]);}
bool cmp(arr x,arr y)
{
    return x.z==y.z?x.col<y.col:x.z<y.z;
}
bool check(int x)
{
    int i;
    ans=-x*need;
    for (i=1;i<=n;i++)fa[i]=i;
    for (i=1;i<=m;i++)
    {
        b[i]=a[i];
        if (b[i].col==0)b[i].z+=x;
    }
    sort(b+1,b+m+1,cmp);
    int k=0,num=0;
    for (i=1;i<=m;i++)
    {
        int fx=getfa(b[i].x),fy=getfa(b[i].y);
        if (fx!=fy)
        {
    if(b[i].col==0&&num==need)continue;//为什么加了这句话就WA了,不是恰好need条吗???
            fa[fx]=fy;
            ans+=b[i].z;
            k++;
            if (b[i].col==0)num++;
            if (k==n-1)break;
        }
    }
    return num>=need;
}
int main()
{
    int i;
    scanf("%d%d%d",&n,&m,&need);
    for (i=1;i<=m;i++)scanf("%d%d%d%d",&a[i].x,&a[i].y,&a[i].z,&a[i].col),a[i].x++,a[i].y++;
    int l=-105,r=105;
    while (l<=r)
    {
        int mid=(l+r)/2;
        if (check(mid))
        {
            l=mid+1;
            anss=ans;
        }else r=mid-1;
    }
    printf("%d",anss);
}

QAQ

@team109 2019-04-13 10:25 回复 举报

去你的萌新

去你的萌新

去你的萌新

去你的萌新

去你的萌新

去你的萌新

去你的萌新

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



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