洛谷P2323 [HNOI2006] 公路修建问题

yiweixxs / 2024-10-09 / 原文

Problem

给出n个点、m条边的无向连通图，每条边具有2个边权，一高一低，我们需要选择若干条边，使得图连通的情况下选择至少k条较高边权，输出选择的边中，边权最大值的最小值，输出答案的一半（保证偶数）

Slove

假设每条边只具有1条边权，答案显而易见，跑一遍最小生成树即可，因为最小生成树就是最小瓶颈树
但是如果存在较高边权且需要选至少k个，该怎么办呢？
注意到，Kruskal算法的本质就是贪心，每次选择最小的边，如果二点未连通，则用并查集合并，否则跳过，直到选择n-1条边
所以此时我们可以将所有边权都遍历一遍，当选择较高边权时k-1,如果k=还需要选择的边时，跳过所有较低边权......吗?
不难发现，此时最小生成树=最小瓶颈树不再适用，但我们可以按照这种贪心思路，优先选择k条较高边权，然后再根据需要选择剩下的边权(也包括较高边权，因为有时某一条边的较低边权可能比另一条边的较高边权还要高!)。因为k条高级边始终是要选择的，且高于低级边权。
时间复杂度就是Kruskal的时间复杂度，为$O(nlogn)$

Code

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstring>
#include<cstdlib>
#include<list>
#include<map>
#include<queue>
#include<stack>
#include<vector>
using namespace std;
int n,k,m,ans;
int f[10005];
struct p{
    int st,to,w,idx;
    bool type;
};
vector<p> g,road;
bool cmp(p a,p b){
    if(a.w!=b.w)
        return a.w<b.w;
    return a.type>b.type;
}
bool cmp1(p a,p b){
    return a.idx<b.idx;
}
int find(int u){
    if(f[u]==u)return u;
    return f[u]=find(f[u]);
}
bool same(int u,int v){
    return find(u)==find(v);
}
bool unit(int u,int v){
    if(same(u,v))return false;
    f[find(u)]=v;
    return true;
}
void kruskal(){
    int edge=n-1;
    for(int i=0;i<g.size();i++){
        if(k>0&&!g[i].type){
            continue;
        }
        if(k==0){
            i=0;
            k--;
        }
        if(unit(g[i].st,g[i].to)){
            k-=g[i].type;
            edge--;
            ans=max(ans,g[i].w);
            road.push_back(g[i]);
        }
        if(!edge)break;
    }
}
int main(){
    cin>>n>>k>>m;
    for(int i=1;i<=n;i++)f[i]=i;
    for(int i=1,st,to,w1,w2;i<m;i++){
        cin>>st>>to>>w1>>w2;
        g.push_back({st,to,w1,i,1});
        g.push_back({st,to,w2,i,0});
    }
    sort(g.begin(),g.end(),cmp);
    kruskal();
    cout<<ans<<endl;
    sort(road.begin(),road.end(),cmp1);
    for(int i=0;i<road.size();i++){
        int type;
        if(road[i].type==1)type=1;
        else type=2;
        cout<<road[i].idx<<" "<<type<<endl;
    }
    return 0;
}