题目：tree
思路：
假设给所有百边加上一个值mid，此时刚好的最小生成树用了Need条百边，那么此时所求的解为s-mid*need，其中s为最小生成树大小。
此时二分mid即可。
只是不知道为什么代码比别人的长很多Orz……
代码：
#include<bits/stdc++.h>
using namespace std;#define maxn 50000
#define maxm 100000
#define inf 100struct Edge {int x,y,z,col;Edge() {}Edge(int xx,int yy,int zz,int c) {x=xx,y=yy,z=zz,col=c;}bool operator < (const Edge& oth) const {return z<oth.z||(z==oth.z&&col<oth.col);}
};int n,m,Need;
Edge a[maxm+5];
Edge b[maxm+5];int fa[maxm+5]={
0};
int s=0;void readin() {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].col);}
}void add(int x) {for(int i=1; i<=m; i++) {b[i]=a[i];if(!a[i].col) b[i].z+=x;}
}int find(int x) {if(fa[x]==-1) return x;else return fa[x]=find(fa[x]);
}int kruskal() {int ans=0;s=0;for(int i=1;i<=m;i++) {int fa1=find(b[i].x),fa2=find(b[i].y);if(fa1!=fa2) {fa[fa1]=fa2;ans+=(!b[i].col);s+=b[i].z;}}return ans;
}bool check(int x) {add(x);sort(b+1,b+m+1);memset(fa,-1,sizeof(fa));int ans=kruskal();return ans>=Need;
}int binsearch() {int l=-inf,r=inf;while(l+1<r) {int mid=l+(r-l)/2;if(check(mid)) l=mid;else r=mid;}if(check(l+1)) l++;if(!check(l)) l--;return l;
}int main() {readin();int ans=binsearch();check(ans);printf("%d",s-ans*Need);return 0;
}