Two Famous Companies

Time Limit: 50000/15000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1092    Accepted Submission(s): 322 Problem Description In China, there are two companies offering the Internet service for the people from all cities: China Telecom and China Unicom. They both are planning to build cables between cities. Obviously, the government wants to connect all the cities in minimum costs. So the minister of finance Mr. B wants to choose some of the  cable plans from the two companies and calculate the minimum cost needed to connect all the cities. Mr. B knows that N-1 cables should be built in order to connect all N cities of China. For some honorable reason, Mr. B should choose K cables from the China Telecom and the rest N-1-K cables from the China Unicom. Your job is to help Mr. B determine which cables should be built and the minimum cost to build them. You may assume that the solution always exists.   Input Each test case starts with a line containing the number of cities N (1 <= N <= 50,000), number of cable plans M (N-1 <= M <= 100,000) and the number of required  cables from China Telecom K (0 <= K <= N-1). This is followed by M lines, each containing four integers a, b, c, x (0 <= a, b <= N-1, a != b, 1 <= c <= 100, x in {0,1} indicating the pair of cities this cable will connect, the cost to build this cable and the company this cable plan belongs to. x=0 denotes that the cable plan belongs to China Telecom and x=1 denotes that the cable plan is from China Unicom.   Output For each test case, display the case number and the minimum cost of the cable building.   Sample Input 2 2 1 0 1 1 1 0 1 2 0 2 2 0 0 1 1 1 0 1 2 0   Sample Output Case 1: 2 Case 2: 1 Hint In the first case, there are two cable plans between the only two cities, one from China Telecom and one from China Unicom. Mr. B needs to choose the one from China Telecom to satisfy the problem requirement even the cost is higher. In the second case, Mr. B must choose the cable from China Unicom, which leads the answer to 1.   这是一道最小生成树 和 二分查找结合的题目，最开始题目看不懂，后来在大佬的分析之下懂了。 题意是 有 a公司和b公司两家要接网线，求最小花费。但是这道题最大的问题在于它给了一个k，要求a公司刚好要有接k条线。 所以学长教我的思路是，给a的线路加权值，使得这个最小生成树上a的线路数是k。 而为了找到一个最合适的权值让它达到这个要求，就用到了二分法。 定义一个left 和 一个 right。因为c的值为0 - 100 ，所以让left = -100，right = 100。 然后二分给你的树传这个权值，然后给所有a的线路的值加上这个权值，再进行操作，最后判断a的条数是否满足k，若比k 小，则让你的权值向左查找，反则向右。 输入 第一行 输入 n m k 表示有n个地点，m种路线，a一定要接k条； 接下来 m行 输入 a,b,c,d 分别表示 a 到 b 花费 c ，该路来源 d 公司  // 0表示a公司，1表示b公司

下边展示一下AC代码

#include<bits/stdc++.h> using namespace std; #define INF 0xFFFFFFF int n,m,k,cot,dis[50010],tt; int vis[100010] = {0}; struct node{ int a,b,c,x; }e[100010]; bool cmp(node a,node b){ 把所有的路线根据权值排序，若权值相等，则a线路优先输出 if(a.c != b.c) return a.c < b.c; //选择花费少的返回 return a.x < b.x; //相同情况选择电信 即 0 } int root(int a){ if(dis[a] == -1) return a; return dis[a] = root(dis[a]); // 一直往回找 } bool kru(int z){ for(int i = 0;i < m;i++) // 把a的所有路线加上权值 if(e[i].x == 0) e[i].c += z; sort(e,e + m,cmp); //把所有的路线根据权值排序，若权值相等，则a线路优先输出 memset(dis,-1,sizeof(dis)); // int edge = 0; //用来记录已经使用的边数 tt = n - 1; // 用来记录a的边数 cot = 0; // 用来记录权值合 for(int i = 0;i < m;i++){ int da = root(e[i].a); // 这一段是把e里面的a 和 b 建立起前后关系 int db = root(e[i].b); if(da != db){ // a 和 b 不同 dis[da] = db; // 让 b 作为 a 的后继 cot += e[i].c; // 花费加 tt -= e[i].x; // a的边数 if(++edge == (n - 1)) //接完结束 break; } } for(int i = 0;i < m;i++) //把加过的权值恢复 if(e[i].x == 0) e[i].c -= z; return tt >= k; //若 a的边数大于等于 k 返回1 } int main(){ int cas = 1; while(~scanf("%d %d %d",&n,&m,&k)){ for(int i = 0;i < m;i++) scanf("%d %d %d %d",&e[i].a,&e[i].b,&e[i].c,&e[i].x); int l = -100,r = 100,mid,ans = INF; while(l <= r){ mid = (l + r) / 2; if(kru(mid)){ //择中值放进树里 若是a的边数多了，那就改变l，使二分范围向右，变大权值 l = mid + 1; ans = cot - k * mid; }else // a的边数少了 改变r ，使二分范围向左 减小权值 r = mid - 1; } printf("Case %d: %d\n",cas++,ans); } }