题解 P6951【[ICPC2018 WF]Wireless is the New Fiber】

feecle6418 · 2021-11-04 17:02:43 · 题解

标题倒装句好评

首先把所有点的度数减一，那么给定度数序列，能构造出合法的树，当且仅当 \sum d_i=n-2。下面的构造证明了这一点。

• 方法：把所有点按度数从小到大排序，对每个点 x，找到其后面第一个度数非零（注意度数已经减一）的点 y，连接 (x,y)，把 y 的度数减一。

那么原问题就转化为：

• 给定一些度数，请你选出最多的度数，满足和不超过 n-2。（因为如果还没达到 n-2 可以再用剩下的一个点补齐）

排序后从小到大选即可。注意输出格式比较毒瘤。

#include <bits/stdc++.h>
using namespace std;
int n,m,d[10005],pl[10005];
int main(){
    cin>>n>>m;
    for(int i=1,x,y;i<=m;i++)cin>>x>>y,d[x]++,d[y]++;
    for(int i=0;i<n;i++)pl[i]=i,d[i]--;
    sort(pl,pl+n,[](int x,int y){return d[x]<d[y];});
    int s=0,ans=0;
    for(int i=0;i<n;i++){
        if(s+d[pl[i]]>n-2)break;
        s+=d[pl[i]],ans++;
    }
    cout<<n-ans<<'\n'<<n<<' '<<n-1<<'\n';
    for(int i=ans;i<n;i++){
        if(s==n-2)d[pl[i]]=0;
        else d[pl[i]]=1,s++;
    }
    sort(pl,pl+n,[](int x,int y){return d[x]<d[y];});
    for(int i=0,j=0;i+2<n;i++){
        while(!d[pl[j]])j++;
        d[pl[j]]--,cout<<pl[i]<<' '<<pl[j]<<'\n';
    }
    cout<<pl[n-2]<<' '<<pl[n-1]<<'\n';
}