题解：CF1082D Maximum Diameter Graph

· · 题解

题解：CF1082D Maximum Diameter Graph

可能是一种很直观、保险的做法，但是时间复杂度较劣。

首先，直径的端点一定是叶子，如果存在一个满足度数限制的连通图，那么它的任意一棵生成树仍然满足度数限制，且对于任意连通图，取其一棵生成树后，任意两点间的距离不会减小（因为删边可能使路径变长），因此生成树的直径不小于原图的直径，因此只需要考虑构造一棵树。我们可以从大到小枚举直径长度。为了使直径最大，我们应该让尽量多的点放在直径路径上，其余点作为叶子挂在直径路径上的点旁边作为枝叶。注意度数上界 a_i=1 的点无法作为直径的链的中间部分，只能够作为直径的端点或者是挂在直径上的叶子，因此，我们可以想出构造策略：

策略想出来了怎么判定无解呢？我们可以使用大根堆存储还可以连接的点，每次取出一个，将除直径以外的点连接上去如果还可以连接就把他放回去（除直径以外的点和堆中提取出的点都可以放回去），如果在一些点未连接上时堆空了则代表该直径长度无法构造出合法的树则跳过，去枚举更短的直径。为什么用大根堆？贪心策略，每次取出剩余可连度数最大的点，防止出现假无解情况。

建边就很简单了，在每次取出堆中元素并连接时就可以使用任意建边的数据结构建边，最后跑一次搜索就可以了。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=1111;
int n;
int a[N],b[N];
vector<int>q;//起终点（度1）
vector<int>p;//衔接点or非径点（度2及上） 
vector<int>g[N];//树 
bool cmp(int x,int y){
    return a[x]<a[y];
}
bool _cmp(int x,int y){
    return a[x]>a[y];
}
void dfs(int u,int dad){
    for(int i=0;i<g[u].size();i++){
        int v=g[u][i];
        if(v==dad){
            continue;
        }
        printf("%d %d\n",u,v);
        dfs(v,u);
    }
} 
int main(){
//  freopen("diameter.in","r",stdin);
//  freopen("diameter.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        b[i]=a[i];
        if(a[i]==1){
            q.push_back(i);
        }else{
            p.push_back(i);
        }
    }
    sort(p.begin(),p.end(),_cmp);
    if(q.size()<2){
        while((!p.empty())&&q.size()<2){
            q.push_back(p[p.size()-1]);
            p.pop_back();
        }
    }
    sort(p.begin(),p.end(),cmp);
    sort(q.begin(),q.end(),_cmp);
    priority_queue<pair<int,int>>dl;
    for(int i=p.size();i>=0;i--){
        for(int j=1;j<=n;j++){
            a[j]=b[j];
            g[j].clear();
        }
        int suml=0;
        int sumr=0;
        int last=q[0];
        a[q[0]]--;
        for(int j=0;j<i;j++){
//          cerr<<last<<" "<<p[j]<<"\n";
            g[last].push_back(p[j]);
            g[p[j]].push_back(last);
            a[p[j]]-=2;
            if(a[p[j]]>0){
                dl.push({a[p[j]],p[j]});
            }
            last=p[j];
        }
        g[last].push_back(q[1]);
        g[q[1]].push_back(last);
        a[q[1]]--;
        bool flag=0;
        for(int j=i;j<p.size();j++){
            if(dl.empty()){
                flag=1;
                break;
            }
            int u=dl.top().second;
            dl.pop();
            // cerr<<u<<" "<<p[j]<<"\n";
            g[u].push_back(p[j]);
            g[p[j]].push_back(u);
            a[u]--;
            if(a[u]>0){
                dl.push({a[u],u});
            }
            a[p[j]]--;
            if(a[p[j]]>0){
                dl.push({a[p[j]],p[j]});
            }
        }
        for(int j=2;j<q.size();j++){
            if(dl.empty()){
                flag=1;
                break;
            }
            int u=dl.top().second;
            dl.pop();
            g[u].push_back(q[j]);
            g[q[j]].push_back(u);
            a[u]--;
            if(a[u]>0){
                dl.push({a[u],u});
            }
            a[q[j]]--;
        }
        if(flag){
            continue;
        }
        printf("YES %d\n%d\n",i+1,n-1);
        dfs(1,0);
        return 0;
    }
    printf("NO");
    return 0;
}  //