记录编号 |
437170 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
题目名称 |
[国家集训队 2012] tree(陈立杰) |
最终得分 |
100 |
用户昵称 |
天亮说晚安· |
是否通过 |
通过 |
代码语言 |
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);
}