D. Maximum Diameter Graph
一颗树具有n个结点,那么这棵树内的线段有n-1条(可以把树枝一个个掰下来,然后拼成)。
此题给了一些点,然后设置了每一个点的度的最高上限。
如果是度为1的点,只能接到别的点的上面,不能作为中转结点同时去连接两个结点。
而如果是度大于等于2的结点,就不单可以作为中转站,还可以去收留收不下去的结点。
这里直径的说明,可以联系到树的直径(两遍dfs,用的算法是不一样的,但定义上差不多)。
基本思路是通过这些度大于或等于2的结点去搭建一个整体的框架,然后再把度为1的结点连到两旁,再把剩余的结点收留到其他能够去继续容纳点的结点中去。
#include <bits/stdc++.h>
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
using namespace std;
const int N = 6E2;
int A[N];
vector<int > pone,pmore;
int main()
{
int n,sum=0;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>A[i];
if(A[i]==1)
pone.push_back(i);
else
pmore.push_back(i);
sum+=A[i];
}
if(sum>=2*(n-1))
{
int maxlen=(pmore.size()-1)+min(int(pone.size()),2);
cout<<"YES "<<maxlen<<endl<<n-1<<endl;
for(int i=1;i<pmore.size();i++)
{
cout<<pmore[i]<<" "<<pmore[i-1]<<endl;
A[pmore[i]]--;A[pmore[i-1]]--;
}
if(pone.size()==1)
cout<<pone[0]<<" "<<pmore[0];
else if(pone.size()==2)
cout<<pone[0]<<" "<<pmore[0]<<endl<<pone[1]<<" "<<pmore[pmore.size()-1];
else if(pone.size()>=3)
{
cout<<pone[0]<<" "<<pmore[0]<<endl<<pone[1]<<" "<<pmore[pmore.size()-1]<<endl;
A[pmore[0]]--;A[pmore[pmore.size()-1]]--;
int cur=0;
for(int i=2;i<pone.size();i++)
{
while(cur<pmore.size()&&A[pmore[cur]]==0)
cur++;
cout<<pone[i]<<" "<<pmore[cur]<<endl;
A[pone[i]]--;A[pmore[cur]]--;
}
}
}
else
cout<<"NO";
return 0;
}