洛谷P2798 爆弹虐场

题目描述

某年某月某日，Kiana 结识了一名爆弹虐场的少年。

Kiana 仗着自己多学了几年OI，所以还可以勉勉强强给这位少年讲一些自己擅长的题。具体来说，Kiana 先给这位少年灌输了n 个毫不相干的知识点，然后再通过自己的[数据删除]技术把这些知识点强行联系在一起。

由于这位少年有着爆弹虐场的实力，所以对于每个Kiana 准备强行构造的联系，他都能够自己想出来，不过会花费更多的时间。具体来说，Kiana 一共有m 个联系，每个联系可以把两个不相干的知识点连在一起，如果由Kiana 直接来讲第i 个联系，需要花费ti 的时间，而如果由少年自己想出来，则需要花费Ti 的时间。

为了偷懒，Kiana 只需要自己讲的或少年想出来的联系能刚好把知识点全部直接或间接串在一起就可以了。但为了保证教学质量， Kiana 觉得至少有k 个联系需要少年自己想出来。由于Kiana 耐心有限，她希望无论是自己讲或是少年自己想，构造的联系中花费时间最长的一个用时最短。

现在Kiana 想知道，满足这些条件的情况下，构造的联系中耗时最长的一个的最短用时是多少。由于她不会算，所以希望由你告诉她。

输入输出格式

输入格式：

输入文件包括m+1 行。

第一行包含三个正整数n,k 和m，分别表示知识点的数量，Kiana 希望少年自己想出来的联系的数量和联系的总数量。

接下来m 行，每行包含四个正整数a,b,Ti 和ti，表示在知识点a 和b 之间可以构造出一个联系，这个联系由少年自己想出来需要花费 Ti 的时间，而Kiana 直接讲出来需要花费ti 的时间。

输出格式：

输出文件包括一行。

第一行包含一个正整数，表示构造的联系中耗时最长的一个的最短用时。

输入输出样例

输入样例#1：

输出样例#1：

说明

对于30%的数据，1<=n<=10，n-1<=m<=15，

对于60%的数据，1<=n<=500，n-1<=m<=1000，

对于100%的数据，1<=k<n<=10000，n-1<=m<=20000，

1<=ti<Ti<=10^6。

数据保证一定存在可行解。

/*
    耗时最长的一个的最短用时,二分答案
    得到一个期望答案mid后，先看看符合要求的Ti的个数是否大于等于k，如果不是，就直接返回0
    如果是，就将符合要求的边，跑一边克鲁斯卡尔看是否能跑出最小生成树来（判断图的连通性），可以的话，返回1，否则返回0 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define maxn 20010
using namespace std;
int n,k,m,mid;
struct node{
    int from,to,v;
    bool operator < (const node b)const{
        return v<b.v;
    }
}e1[maxn],e2[maxn];
int f[maxn];
int find(int x){
    if(x==f[x])return x;
    else return f[x]=find(f[x]);
}
bool connect(int x,int y){
    int f1=find(x),f2=find(y);
    if(f1==f2)return 0;
    else {
        f[f1]=f2;
        return 1;
    }
}
bool check(){
    int l=1,r=m,md,cnt=0;
    while(l<=r){
        md=(l+r)>>1;
        if(e2[md].v<=mid)cnt=md,l=md+1;
        else r=md-1;
    }
    if(cnt<k)return 0;
    for(int i=1;i<=n;i++)f[i]=i;
    cnt=0;
    for(int i=1;i<=m;i++){
        if(e2[i].v>mid)break;
        int x=e2[i].from,y=e2[i].to;
        if(connect(x,y))cnt++;
        if(cnt>=n-1)return 1;
    }
    for(int i=1;i<=m;i++){
        if(e1[i].v>mid)break;
        int x=e1[i].from,y=e1[i].to;
        if(connect(x,y))cnt++;
        if(cnt>=n-1)return 1;
    }
    return 0;
}
int main(){
    freopen("Cola.txt","r",stdin);
    scanf("%d%d%d",&n,&k,&m);
    int x,y,l=0x7fffffff,r=-0x7fffffff;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d%d",&x,&y,&e2[i].v,&e1[i].v);
        e1[i].from=e2[i].from=x;
        e1[i].to=e2[i].to=y;
        l=min(l,min(e1[i].v,e2[i].v));
        r=max(r,max(e1[i].v,e2[i].v));
    }
    int ans=0x7fffffff;
    sort(e1+1,e1+m+1);sort(e2+1,e2+m+1);
    while(l<=r){
        mid=(l+r)>>1;
        if(check())ans=mid,r=mid-1;
        else l=mid+1;
    }
    printf("%d",ans);
}