记录编号 437170 评测结果 AAAAAAAAAAAAAAAAAAAA
题目名称 [国家集训队 2012] tree(陈立杰) 最终得分 100
用户昵称 Gravatar天亮说晚安· 是否通过 通过
代码语言 C++ 运行时间 1.715 s
提交时间 2017-08-13 18:59:57 内存使用 6.80 MiB
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define maxn 50005
using namespace std; 
typedef long long ll;
inline ll read(){
     char x=getchar();ll sum=0,f=1;
     while(x<'0'||x>'9'){if(x=='-')f=-1;x=getchar();}
     while(x>='0'&&x<='9'){sum=sum*10+x-'0';x=getchar();}
     return f*sum;
}

ll n,m,num;
struct Edge{
     ll size;
	 struct node{
	     ll u,v,w,B;
	     bool operator <(const node & a) const{
		     if(w<a.w)  return 1;
			 if(w>a.w)  return 0;
			 if(B&&!a.B) return 1;
			 return 0; 
		 }
	 }edge[maxn*2];
	 inline void add(ll u,ll v,ll w,ll biao){
	     edge[++size].u=u;edge[size].v=v;
	     edge[size].w=w;edge[size].B=biao;
	 }
}all;
struct pp{
     ll u,v,w,se;
}bian[maxn*2];
ll cnt,f[maxn],sum;

inline ll find(ll x){
     if(f[x]==x)  return x;
     f[x]=find(f[x]);
     return f[x];
}

inline void kruscal(){
	 memset(f,0,sizeof(f));
     for(ll i=1;i<=n;i++) f[i]=i;
	 sort(all.edge+1,all.edge+m+1);
	 ll oo=0;
     for(ll i=1;i<=m;i++){
	     ll u=all.edge[i].u,v=all.edge[i].v;
	     ll fx=find(u),fy=find(v);
	     if(fx!=fy){
		     f[fx]=fy;  oo++;
			 sum+=all.edge[i].w;
		     if(all.edge[i].B)  cnt++;
		 }
		 if(oo==n-1)  break;
	 }
}

inline void check(ll shu){
	 memset(all.edge,0,sizeof(all.edge));
	 all.size=0;
     for(ll i=1;i<=m;i++){
     	 ll w=bian[i].w;  bool biao=0;
	     if(!bian[i].se)  w+=shu,biao=1; 
	     all.add(bian[i].u,bian[i].v,w,biao); 
	 }
	 cnt=sum=0;  kruscal();
}

inline ll getans(){
     ll l=-101,r=101,mid,ans; 
     while(l<r){
	     mid=(l+r)>>1;  check(mid);
	     if(cnt==num) return mid;
	     if(cnt>num)  ans=mid,l=mid+1;
	     else         r=mid;
	 }   
	 check(ans); if(cnt<num){check(ans+1);ans=ans+1;}
	 return ans;
}

int main(){
freopen("nt2012_tree.in","r",stdin);
freopen("nt2012_tree.out","w",stdout);
     n=read(),m=read(),num=read();
     for(ll i=1;i<=m;i++){
	    ll x=read(),y=read(),z=read(),w=read();
	    bian[i].u=x+1,bian[i].v=y+1;
		bian[i].w=z,bian[i].se=w;  
	 }
	 ll Q=getans();
	 printf("%lld",sum-Q*num);
}