题解归档 - cf362D

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf362D
• 本地来源：problems/cf362D/idea.md
• 题目链接：https://codeforces.com/contest/362/problem/D
• 原始标题：CF362D — Fools and Foolproof Roads

思路

CF362D — Fools and Foolproof Roads

题意

n 城、m 条已有道路（带权）。需恰好新建 p 条道路，使最终连通块数为 q。

新建 (u,v) 时：

• 若 u,v 已在同一连通块：新边权 = 1000；
• 否则：新边权 = min(10^9, S+1)，其中 S 为两连通块内已有道路权值之和；建完后两块合并。

求可行方案并最小化新建道路总权值；输出建边顺序。

做法

1. DSU 统计初始连通块数 c、每块道路权和 S、代表点 u1/u2（u2 为第二城，若块大小≥2）。
2. 合并次数 k = c − q。若 c < q 或 k > p → NO。
3. 若 p − k > 0（需建同块边）但不存在大小≥2 的块（且 k=0）→ NO。
4. 跨块边：每次取 S 最小的两块合并，代价 min(10^9, S1+S2+1)（Huffman 贪心）。
5. 同块边：在最大块内重复输出 u1–u2，每条代价 1000。
6. 建完后若仍缺同块边但无 u2 → NO。

复杂度

O((n+m) α(n) + k log c)。

验证

• 样例 1/2/3 通过；
• Kali 不可达，本机 g++ 跑样例。

代码

来源：problems/cf362D/solution.cpp

/* Author: likely
 * Time: 2026-06-08 04:50:58
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=100005,LIM=1000000000;
ll f[maxn+5],sz[maxn+5],s[maxn+5],rep[maxn+5],n,m,p,q,i,j,k,x,y,zc,pd,cur,dq,cnt,ans;
ll find(ll x){
    if(f[x]!=x) f[x]=find(f[x]);
    return f[x];
}
struct nd{
    ll w,id;
    bool operator<(nd o)const{
        if(w!=o.w) return w>o.w;
        return id>o.id;
    }
};
priority_queue<nd>pq;
vector<pair<ll,ll>>out;
int main(){
    cin>>n>>m>>p>>q;
    for(i=1;i<=n;i++) f[i]=i,sz[i]=1,rep[i]=i,s[i]=0;
    for(i=1;i<=m;i++){
        cin>>x>>y>>zc;
        x=find(x),y=find(y);
        if(x==y) s[x]+=zc;
        else{
            if(sz[x]<sz[y]) swap(x,y);
            f[y]=x;
            sz[x]+=sz[y];
            s[x]+=s[y]+zc;
        }
    }
    ll c=0,su=0,sv=0,msz=0;
    for(i=1;i<=n;i++){
        if(find(i)!=i) continue;
        c++;
        pq.push({s[i],rep[i]});
        if(sz[i]>=2){
            ll u=0,v=0;
            for(j=1;j<=n;j++) if(find(j)==i){
                if(!u) u=j;
                else{v=j;break;}
            }
            if(sz[i]>msz or (sz[i]==msz and u<su)){
                msz=sz[i],su=u,sv=v;
            }
        }
    }
    ll need=c-q;
    if(need<0 or need>p){
        cout<<"NO\n";
        return 0;
    }
    ll y=p-need;
    if(y>0 and su==0){
        cout<<"NO\n";
        return 0;
    }
    for(i=1;i<=need;i++){
        nd a=pq.top();pq.pop();
        nd b=pq.top();pq.pop();
        cur=min(LIM,a.w+b.w+1);
        out.push_back({a.id,b.id});
        su=a.id,sv=b.id;
        pq.push({a.w+b.w+cur,a.id});
    }
    for(i=1;i<=y;i++) out.push_back({su,sv});
    cout<<"YES\n";
    for(autoe:out) cout<<e.first<<" "<<e.second<<"\n";
    return 0;
}