亟隐

朝不闻道,夕亦死可矣

07/26
22:33
图论 算法区

HDU 4253 Two Famous Companies

地址:戳这里

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

二分最大的s,使得全部0类的边都增加s后最小生成树用到0类的边有k条或以上。

代码:戳这里