~~stm萌妹~~
by Lstdo @ 2018-11-02 14:07:05
你为什么要强调自己是个萌妹？
by 乙津梦 @ 2018-11-02 14:07:21
要求爆照
by 乙津梦 @ 2018-11-02 14:07:46
~~orz萌妹~~
by Thosaka_Forest @ 2018-11-02 14:08:01
哎呀 萌妹贴错代码啦~
```cpp
#include<bits/stdc++.h>
#define N 50005
#define M 100005
using namespace std;
struct Edge
{
int from,to,color,val;
}edge[M];
template <class T>
inline void read(T &x)
{
x=0;
static char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
}
int n,m,need,ans;
int l,r,father[N];
inline int getfather(int x)
{
if(father[x]==x) return x;
father[x]=getfather(father[x]);
return father[x];
}
inline bool cmp(const Edge &x,const Edge &y)
{
if(x.val==y.val) return x.color<y.color;
return x.val<y.val;
}
inline bool check(int del)
{
for(int i=1;i<=m;i++) if(edge[i].color==0) edge[i].val+=del;
for(int i=1;i<=n;i++) father[i]=i;
sort(edge+1,edge+m+1,cmp);
int white=0,sum=0,cnt=0,flag;
for(int i=1;i<=m;i++)
{
int fx=getfather(edge[i].from),fy=getfather(edge[i].to);
if(fx!=fy)
{
father[fx]=fy; sum+=edge[i].val; cnt++;
if(edge[i].color==0) white++;
if(cnt==n-1)
{
if(white>=need) ans=sum-del*need,flag=1;
else flag=0;
break;
}
}
}
for(int i=1;i<=m;i++) if(edge[i].color==0) edge[i].val-=del;
return flag;
}
int main()
{
read(n); read(m); read(need);
for(int i=1;i<=m;i++)
{
read(edge[i].from); read(edge[i].to); edge[i].from++; edge[i].to++;
read(edge[i].val); read(edge[i].color);
r=max(r,edge[i].val+1);
}
l=-r;
while(l<r)
{
int mid=(l+r)/2;
if(check(mid)) l=mid+1;
else r=mid;
}
cout<<ans;
return 0;
}
```
by Patrickpwq @ 2018-11-02 14:08:48
一般来说学oi的不是恐龙就是dark♀爷
by 乙津梦 @ 2018-11-02 14:08:54
@[以梦为名](/space/show?uid=94511) 人家真是萌妹啦
by Patrickpwq @ 2018-11-02 14:09:25
爆照！
by Lstdo @ 2018-11-02 14:09:44
@[Patrickpwq](/space/show?uid=60299) 把裤子脱下来?
by 乙津梦 @ 2018-11-02 14:10:24
爆照+1
by Thosaka_Forest @ 2018-11-02 14:10:26