<题目链接>
题目大意：
给你一些点的最大度数，让你构造一张图，使得该图的直径最长，输出对应直径以及所有的边。
解题分析：
一道比较暴力的构造题，首先，我们贪心的想，要使图的直径最长，肯定是尽可能的将所有的顶点连在同一条链上，并且，所有度数为1的点都只能作为最外围的点。所以，基本思想就是先将两个度为1的顶点放在链的两端(如果有的话)，然后所有度>=2的点放在链的中间，建好链之后，再将多余的度为1的点挂在链上最大度数未满的点上。
#include <bits/stdc++.h> using namespace std; const int N = 505; int n,ind[N]; struct Node{ int ind,loc; bool operator < (const Node &tmp){ return ind>tmp.ind; } }; vector<Node>vec1,vec; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ int numd;scanf("%d",&numd); if(numd==1)vec1.push_back(Node{numd,i}); if(numd>1)vec.push_back(Node{numd,i}); } if(vec1.size()<=2){ if(vec1.size()==0){ printf("YES %d\n",vec.size()-1); printf("%d\n",vec.size()-1); int u=vec[0].loc; for(int i=1;i<vec.size();i++){ int v=vec[i].loc;printf("%d %d\n",u,v); u=v; } }else { if(vec1.size()==1){ printf("YES %d\n",vec.size()); printf("%d\n",vec.size()); int u=vec1[0].loc; for(int i=0;i<vec.size();i++){ int v=vec[i].loc;printf("%d %d\n",u,v); u=v; } }else if(vec1.size()==2){ printf("YES %d\n",vec.size()+1); printf("%d\n",vec.size()+1); int u=vec1[0].loc; for(int i=0;i<vec.size();i++){ int v=vec[i].loc;printf("%d %d\n",u,v); u=v; } printf("%d %d\n",vec[vec.size()-1].loc,vec1[1].loc); } } }else { //如果度为1的点多于2个 int sum=0; for(int i=0;i<vec.size();i++){ vec[i].ind-=2; sum+=vec[i].ind; } if(sum<vec1.size()-2)return puts("NO"),0; printf("YES %d\n",vec.size()+1); printf("%d\n",vec.size()+1+vec1.size()-2); int u=vec1[0].loc; for(int i=0;i<vec.size();i++){ int v=vec[i].loc;printf("%d %d\n",u,v); u=v; } printf("%d %d\n",vec[vec.size()-1].loc,vec1[1].loc); sort(vec.begin(),vec.end()); int pos=0; for(int i=2;i<vec1.size();i++){ vec[pos].ind--; printf("%d %d\n",vec1[i].loc,vec[pos].loc); if(vec[pos].ind==0)pos++; } } }
Codeforces 1082D Maximum Diameter Graph (贪心构造)
原文：https://www.cnblogs.com/00isok/p/10522323.html