第二个问题的代码分别是这样的
```cpp
inline bool check(int val) {
rep(i,1,n) f[i]=i;tot=num=cnt=sum=0;
R int i=1,j=1;
while(i<=nb&&j<=nh) {
if(b[i].val+val<h[j].val) e[++tot]=b[i++];
else e[++tot]=h[j++];
}
while(i<=nb) e[++tot]=b[i++];
while(j<=nh) e[++tot]=h[j++];
rep(i,1,m) {
int u=e[i].from,v=e[i].to,w=e[i].val,c=e[i].col;
int r1=find(u),r2=find(v);
if(r1==r2) continue ;
f[r1]=r2,++cnt,sum+=w+(!e[i].col)*val;
if(!c) ++num;
if(cnt==n-1) break ;
}
return num<=need;
}
int main() {
n=read(),m=read(),need=read();
int l=0,r=0;
rep(i,1,m) {
int u=read()+1,v=read()+1,w=read(),c=read();
r=max(r,w);
if(c==0) b[++nb]=Edge(u,v,w,c);
else h[++nh]=Edge(u,v,w,c);
}
l=-r;
sort(b+1,b+nb+1),sort(h+1,h+nh+1);
int now=0;
while(l<=r) {
int mid=(l+r)>>1;
if(check(mid)) now=mid,r=mid-1;
else l=mid+1;
}
check(now);
printf("%d",sum-need*now);
return 0;
}
```
```cpp
inline bool check(int val) {
rep(i,1,n) f[i]=i;tot=num=cnt=sum=0;
R int i=1,j=1;
while(i<=nb&&j<=nh) {
if(b[i].val+val<h[j].val) e[++tot]=b[i++];
else e[++tot]=h[j++];
}
while(i<=nb) e[++tot]=b[i++];
while(j<=nh) e[++tot]=h[j++];
rep(i,1,m) {
int u=e[i].from,v=e[i].to,w=e[i].val,c=e[i].col;
int r1=find(u),r2=find(v);
if(r1==r2) continue ;
f[r1]=r2,++cnt,sum+=w;
if(!c) ++num;
if(cnt==n-1) break ;
}
return num<=need;
}
int main() {
n=read(),m=read(),need=read();
int l=0,r=0;
rep(i,1,m) {
int u=read()+1,v=read()+1,w=read(),c=read();
r=max(r,w);
if(c==0) b[++nb]=Edge(u,v,w,c);
else h[++nh]=Edge(u,v,w,c);
}
l=-r;
sort(b+1,b+nb+1),sort(h+1,h+nh+1);
int now=0;
while(l<=r) {
int mid=(l+r)>>1;
if(check(mid)) now=mid,r=mid-1;
else l=mid+1;
}
check(now);
printf("%d",sum);
return 0;
}
```
by mzgwty @ 2020-08-06 17:40:16
第二个问题现在已经得到解决了qwq
by mzgwty @ 2020-08-06 17:46:56
Orz
by A1443356159 @ 2020-08-11 17:47:03