QWQ不得不说 (cf)的(edu round)出这种东西 有点太恶心了
题目大意：给你(n)个点，告诉你每个点的最大度数值（也就是说你的度数要小于等于这个），让你构造一个无向图，使其满足直径最大且包含所有点
一看就是个构造题
QWQ但是细节非常多。
大致上的思路就是，我们考虑把度数大于1的点拿出来，然后构成一条链，剩下的往这条链上挂就行，但是挂的时候要注意，优先往最头上的两个点挂，因为这样可以扩大直径，然后搞一搞就好
QWQ
（其实是强行凑博客文章数目）
记得特判一下只有一个度数大于1，或者没有的情况啊！
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#define mk make_pair
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
const int maxn = 2010;
vector<pair<int,int> > ans;
vector<int> v;
int a[maxn];
int n,m;
bool flag=1;
vector<int> v1;
int tmp;
int ymh;
int main()
{
n=read();
for (int i=1;i<=n;i++)
{//
a[i]=read();
if (a[i]>1) v.push_back(i),tmp+=a[i];
}
for (int i=1;i<=n;i++) if (a[i]==1) v1.push_back(i);
if (v.size()==1)
{
int pos=0;
for (int i=1;i<=n;i++) if (a[i]>1) pos=i;
if (tmp>=n-1)
{
cout<<"YES"<<" "<<min(n-1,2)<<endl;
cout<<n-1<<endl;
for (int i=1;i<=n;i++)
{
if (i!=pos)
{
cout<<i<<" "<<pos<<"
";
}
}
}
else
{
cout<<"NO";
}
return 0;
}
if (v.size()==0)
{
cout<<"NO";
return 0;
}
for (int i=0;i<v.size()-1;i++) ans.push_back(mk(v[i],v[i+1])),a[v[i]]--,a[v[i+1]]--;
ymh = v.size()-1;
if (v1.size()==1)
{
ymh++;
ans.push_back(mk(v[0],v1[0]));
}
int now = 0;
if (v1.size()>=2)
{
ymh+=2;
now = 2;
ans.push_back(mk(v[0],v1[0]));
ans.push_back(mk(v[v.size()-1],v1[1]));
a[v[0]]--;
a[v[v.size()-1]]--;
int i=0;
while (i<v.size() && now<v1.size())
{
while (i<v.size() && a[v[i]]==0) i++;
if (i==v.size()) break;
ans.push_back(mk(v[i],v1[now]));
now++;
a[v[i]]--;
}
}
if (now!=v1.size() && v1.size()>=2)
{
cout<<"NO";
}
else
{
cout<<"YES"<<" "<<ymh<<endl;
cout<<ans.size()<<endl;
for (int i=0;i<ans.size();i++)
{
cout<<ans[i].first<<" "<<ans[i].second<<"
";
}
}
return 0;
}