2015
05-23

# Two Famous Companies

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.

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.

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.

2 2 1
0 1 1 1
0 1 2 0
2 2 0
0 1 1 1
0 1 2 0

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.


#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxm=100010;
const int maxn=50010;
struct node
{
int u,v,w,ty;
}e[maxm];
int r[maxn],n,m,k,ret,telecom;

bool cmpw(node a,node b)
{
if(a.w!=b.w) return a.w<b.w;
return a.ty<b.ty;
}
int root(int a)
{
if(r[a]==-1) return a;
return r[a]=root(r[a]);
}
bool kru(int x)
{
for(int i=0;i<m;i++)
if(e[i].ty==0) e[i].w+=x;
sort(e,e+m,cmpw);
memset(r,-1,sizeof r);
int edge=0;telecom=n-1;ret=0;
for(int i=0;i<m;i++)
{
int ra=root(e[i].u);
int rb=root(e[i].v);
if(ra!=rb)
{
r[ra]=rb;
ret+=e[i].w;
telecom-=e[i].ty;
if(++edge==n-1) break;
}
}
for(int i=0;i<m;i++)
if(e[i].ty==0) e[i].w-=x;
return telecom>=k;
}

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].u,&e[i].v,&e[i].w,&e[i].ty);
int l=-100,r=100,mid,ans=0x3f3f3f3f;
while(l<=r)
{
mid=(l+r)/2;
if(kru(mid)) l=mid+1,ans=ret-mid*k;
else r=mid-1;
}
printf("Case %d: %d\n",cas++,ans);
}
return 0;
}


1. 叨叨小主今日身体不适，若是获假得以休息，自然是极好的。只是奴才们久等小主更新。小主慈悲心肠，望明日可再赏奴才们一期。若是小主无力更新也无妨，奴才不求别的，但愿小主能赏奴才上榜。奴才在这里给小主请安了——叨叨小主万福金安~~PS：叨叨哇~~我追了这么多期，