Tree

solution

求一棵恰好有 $needneed$ 条白边的最小生成树，根据 $MSTMST$ 的求解方法，一条白边是否在 $MSTMST$ 中只与白边的权值有关。所以我们只需对白边进行增量操作即可。假设我们对图中的每条白边的增量为 $xx$ ，$MSTMST$ 中白边的数量记为 $f(x)f(x)$ ，可以易看出 $f(x)f(x)$ 的大小是随 $xx$ 的增大而增大的，满足单调性，考虑二分增量。 那么这道题就可以切了。。。

code

using Simon O_O ;
int n , m , need , ans ;
struct node 
{
	int frm , to , dis ;
	bool col ; 
} ed[maxn << 1] ;
bool operator <(node x , node y)
{
	if(x.dis == y.dis)	return x.col <  y.col ;//权值相同优先选白边
	return x.dis < y.dis ;
} 
int dis[maxn] , Cnt[maxn] , fa[maxn] ;
int find(int x)
{
	if(x == fa[x])	return x ; 
	return fa[x] = find(fa[x]) ; 
}
int kru(int x)
{
	int tot = 0 ;	ans = 0 ; 
	for(int i = 1 ; i <= m ; i++ )
		if(!ed[i].col)	ed[i].dis += x ;
	fa[0] = 0 ; 
	for(int i = 1 ; i <= n ; i++ )	fa[i] = i ;                                         
	sort(ed + 1 , ed + m + 1) ;
	for(int i = 1 ; i <= m ; i++ )
	{
		int u = find(ed[i].frm) , v = find(ed[i].to) ; 
		if(u == v)	continue ; 
		fa[v] = u ; 
		if(!ed[i].col)	tot++ ; 	ans += ed[i].dis ; 		
	}
	for(int i = 1 ; i <= m ; i++ )
		if(!ed[i].col)	ed[i].dis -= x ;
	return tot ;//统计MST中白边个数
}
signed main()
{
	n = read() , m = read() , need = read() ;
	int mid = 0 ;
	for(int i = 1 ; i <= m ; i++ )
	{
		int u , v , w , col ; 
		u = read() , v = read() , w = read() , col = read() ;
		ed[i] = {u , v , w , col}  ; 
	}
	int l = -105 , r = 105 ; 
	int ans2 = 0 ; 
	while(l < r)
	{
		mid = l + r >> 1 ;
		if(kru( mid ) >= need )		l = mid + 1 , ans2 = ans - need * mid ; 
		else r = mid ; 
	}
	cout << ans - need * mid ; 
	return 0 ; 
}