题目意思：给出n个点，m条边，边分为两种，一种是A公司的，一种是B公司的。边上有权值，
问用n-1条边把n个点连起来的最小费用是多少，其中A公司的边刚好有k条。题目保证有解。
题解：题目意思很简单就是求MST且A公司要有且仅有k条边在树中，刚开始做的时候用贪心的方式求
最小生成树结果WA，后来看了下别人的题解，二分出一个最大值delta使得A公司的边加上这个值后再
求MST时A公司的边有大于等于k条，然后答案就是cost of MST - k * delta。思想就是用一个delta去
逼近答案。当delta越大的时候A公司的边就越少，反之越多。所以二分delta可以找到使得A公司刚好取K条边的要求。
#include#include #include using namespace std;struct node{ int u,v,cost; bool operator < (node a)const{ return cost < a.cost; }}arr[2][100005];int father[100005];int n,m,k,num[2],mincost;int find(int x){ if( x != father[x]) return father[x] = find(father[x]); return father[x];}int union_set(int x,int y){ x = find(x); y = find(y); if( x != y){ father[x] = y; return 1; } return 0;}bool check(int delta){ int tel = k,Union = n-k-1; int nn = n,i,j; mincost = 0; for( i = 0; i <= n; i++)father[i] = i; i = j = 0; while( nn > 1 ){ if( j < num[1] && ( i >= num[0] || arr[0][i].cost + delta > arr[1][j].cost)){ if( union_set(arr[1][j].u,arr[1][j].v ) ) { mincost += arr[1][j].cost; nn--; Union--; } j++; } else{ if( union_set(arr[0][i].u,arr[0][i].v ) ){ mincost += arr[0][i].cost + delta; nn--; tel --; } i++; } } return tel <= 0;}int main(){ struct node tmp; int cas = 1; int u,v,cost,x; int l,r,mid,m; freopen("in.txt","r",stdin); while( ~scanf("%d%d%d",&n,&m,&k)){ num[0] = num[1] = r = 0; for(int i = 0; i < m; i++){ father[i] = i; scanf("%d%d%d%d",&tmp.u,&tmp.v,&tmp.cost,&x); arr[x][num[x]++] = tmp; } for( int i = 0; i < 2; i++) sort(arr[i],arr[i]+num[i]); l = -110,r = 110; int res; while( l <= r){ mid = (l+r)>>1; if( check(mid) ){ res = mincost; m = mid; l = mid + 1; } else r = mid - 1; } printf("Case %d: %d\n",cas++,res - m*k); }}