新人求助,Tree I那题,bzoj AC提交WA。。。

回复帖子

@EternalAlexander 2018-12-15 16:58 回复
#include <bits/stdc++.h>
#define maxn 50005

int c[maxn],u[maxn],v[maxn],w[maxn],id[maxn], fa[maxn<<1]={0};
int n, k,m, delta, cost, cnt;

int getf(int x) {return fa[x]?fa[x]=getf(fa[x]):x;}
void merge(int x, int y) {fa[getf(y)]=getf(x);}

int cmp(int a, int b) {
    int wa=w[a]+delta*(c[a]^1), wb=w[b]+delta*(c[b]^1);
    return wa<wb||(wa==wb&&c[a]<c[b]);
}

int check(int x) {
    std::memset(fa,0,sizeof(fa));
    delta=x,cnt=0,cost=0;
    std::sort(id+1, id+m+1, cmp);
    for (int j=1;j<=m;++j) {
        int i=id[j];
        if (getf(u[i])!=getf(v[i])) {

            cnt+=(c[i]^1); merge(u[i], v[i]);
            cost+=w[i]+delta*(c[i]^1);
        }
    }//printf("%d %d %d\n",cnt,delta, cost);
    return cnt>=k;
}

int main() {
//  freopen("a.txt","r",stdin);
    scanf("%d %d %d", &n, &m, &k);
    for (int i=1;i<=m;++i) {
        scanf("%d %d %d %d", &u[i], &v[i], &w[i], &c[i]); id[i]=i;
        u[i]++;v[i]++;
    }int l=-100,r=100,ans;
    while (l<=r) {
        int mid=(l+r)>>1, d=check(mid);
        if (d==0) {
            r=mid-1; 
        }
        if (d==1) {
            l=mid+1;
            ans=cost-delta*k;
        }
    }printf("%d", ans);
    return 0;
}

而且没有数据不知道为啥wa,调了很久一直是35~45。

@wjyyy 2018-12-15 17:04 回复 举报

数组开小理论上会访问到开的下一个数组去……

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



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