# 新人求助，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;
}

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