博客

注意二分初始值

https://www.cnblogs.com/NaVi-Awson/p/7252243.html

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=50000+5,M=100000+5;
int n,m,need;
 
struct edge{int x,y,z,cor;}a[M]; int mid,sum;
bool cmp(edge p,edge q)
 {if(p.z+p.cor*mid==q.z+q.cor*mid) return p.cor<q.cor;
  return  p.z+p.cor*mid<q.z+q.cor*mid;                               
 }
 
int f[N];
int find(int x)
 {if(f[x]==x) return x;
              return f[x]=find(f[x]);
 }
 
inline bool check()
 {for(int i=1;i<=n;i++)  f[i]=i;
  sort(a+1,a+m+1,cmp);
   
  int cnt=0,link=0; sum=0;
   
  for(int i=1;i<=m;i++)
   {int r1=find(a[i].x),r2=find(a[i].y);
    if(r1==r2) continue;
     
    f[r1]=r2;    link++;
     
    sum+=a[i].z; cnt+=a[i].cor;
    if(link==n-1) break;
   }
  return  cnt>=need;
 } 
int main()
 {
 scanf("%d%d%d",&n,&m,&need);    
         
 for(int i=1;i<=m;i++) 
  {scanf("%d%d%d%d",&a[i].x,&a[i].y,&a[i].z,&a[i].cor);
   a[i].x++; a[i].y++; a[i].cor=1-a[i].cor;
  }
     
 int l=-105,r=105,ans=0;    
  
 while(l<=r)
  {mid=(l+r)/2;
   if(check()) ans=sum,l=mid+1;
   else                r=mid-1;
  } 
 printf("%d",ans); 
return 0;
 }