首页 > ACM题库 > HDU-杭电 > HDU 4253-Two Famous Companies-分治-[解题报告]HOJ
2015
05-23

HDU 4253-Two Famous Companies-分治-[解题报告]HOJ

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.

给n个点,m条边的图,每条边要么属于a公司,要么属于b公司。要求一颗最小生成树,条件是其中属于a公司的边数为k。

这题做法很巧妙。

要求最小生成树,但有一定限制,搜索、贪心显然都不对。

要是能找到一种合理的控制方法,使得求MST的过程中可以控制a公司边的数量,那样问题就解决了。

所以我们可以人为给a公司的边加上一定的权值,使得其中一些边不得不退出MST的选择范围内。

如果此时求的mst里a公司的边数>k,那么就要增加权值;边数<k时,权值为负。

所以,通过二分边权值,可以使得求得mst里所含a公司的边数逐渐逼近k,此时记录答案,因为一定有解,所以最终一定是所求答案。

#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;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/u011032846/article/details/40404013