怎么说呢……神奇的二分
每次把白色边加上一个二分的权值，再做最小生成树
如果大于need条边就说明加上的权值太小了需要增大
反之亦然(因为题目保证有解，所以必然会存在这样的一个权值)
注意排序时权值相等时白色边放在前面
#include<cstdio>
#include<algorithm>
using namespace std;
int V,E,need,f[100005],test=0,ne=0;
struct Edge{
int a,b,v,co;
friend bool operator<(Edge a,Edge b){
return a.v==b.v?a.co<b.co:a.v<b.v;
}
}e[100005];
int Find(int x){return x==f[x]?x:f[x]=Find(f[x]);}
void Union(int sa,int sb){
if(sa<sb)f[sb]=sa;
else f[sa]=sb;
}
int Check(int ans){
test=ne=0;
for(int i=1;i<=V;i++)f[i]=i;
for(int i=1;i<=E;i++){
if(!e[i].co)e[i].v+=ans;
}
sort(e+1,e+E+1);
for(int i=1;i<=E;i++){
if(Find(e[i].a)!=Find(e[i].b)){
Union(Find(e[i].a),Find(e[i].b));
test+=e[i].v;
if(!e[i].co)ne++;
}
}
for(int i=1;i<=E;i++){
if(!e[i].co)e[i].v-=ans;
}
return ne>=need;
}
int main(){
freopen("2654.in","r",stdin);
freopen("2654.out","w",stdout);
scanf("%d %d %d",&V,&E,&need);
for(int i=1;i<=E;i++){
scanf("%d %d %d %d",&e[i].a,&e[i].b,&e[i].v,&e[i].co);
e[i].a++;
e[i].b++;
}
int l=-105,r=105,ans;
while(l<=r){
int mid=l+r>>1;
if(Check(mid)){ans=test-need*mid;l=mid+1;}
else r=mid-1;
}
printf("%d\n",ans);
return 0;
}
评论 (0)
