【Educational Codeforces Round 55 (Rated for Div. 2) D. Maximum Diameter Graph】构造+贪心

D. Maximum Diameter Graph

题意

给你n个点的入度上限，用这个要求构造一张图，并满足这个图的最远的两点距离最大

做法

由于最远的两点距离最大而且度数有上限，也就不需要任何松弛操作，
根据贪心思想，肯定尽量少的连边，也就意味着最终答案是一棵树
我们把度数大于等于2的点拽成一条链，之后先在两边添加度数为1的点保证直径最长，之后在中间不断添加度数为1的点就可以了

代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn =1005;
int a[maxn];
int con[maxn][maxn];
struct data
{
    int id;int ind;
}x[maxn];
bool cmp(const data &a,const data &b)
{
    return a.ind<b.ind;
}
int main()
{
    int n;int sum=0;scanf("%d",&n);for(int i=1;i<=n;i++){
    scanf("%d",&x[i].ind);if(x[i].ind==1) sum++;x[i].id=i;}sort(x+1,x+1+n,cmp);int st=-1;for(int i=1;i<=n;i++){
    if(x[i+1].ind>1){
    st=i;break;}}if(st==-1){
    printf("NO\n");return 0;}int pos=st-1;int cnt=0;for(int i=st;i<=n-1;i++){
    con[x[i].id][x[i+1].id]=1;cnt++;x[i].ind--;x[i+1].ind--;}for(int i=n;i>=st;i--){
    int tt=x[i].ind;while(pos!=0&&tt--){
    cnt++;con[x[pos].id][x[i].id]=1;pos--;}if(pos==0) break;}if(pos>0) printf("NO\n");else{
    printf("YES %d\n%d\n",min(n-1,n-st+1),cnt);for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
    if(con[i][j]) printf("%d %d\n",i,j);}}}return 0;
}