# 萌新真的刚学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 回复 举报