D. Maximum Diameter Graph 贪心+图论+模拟

 1 #include<bits/stdc++.h>
 2 #define pb push_back 
 3 #define pii pair<int,int>
 4 #define mkp make_pair
 5 #define S second
 6 #define F first
 7 using namespace std;
 8 const int maxn=2e5+6;
 9 const int inf =0x3f3f3f3f;
10 vector<pii>v;
11 vector<int>v1;
12 int vis[maxn];
13 pii ans[maxn];
14 int main(){
15     int n;
16     scanf("%d",&n);
17     int tmp;
18     for(int i=1;i<=n;i++){
19         scanf("%d",&tmp);
20         if(tmp==1)v1.pb(i);
21         else {
22             v.pb(mkp(tmp,i));
23         }
24     }
25     if(n==2){
26         cout<<"YES "<<2<<endl;
27         cout<<1<<endl;
28         cout<<1<<" "<<2<<endl;
29         return 0;
30     }
31     //cout<<v.size()<<endl;
32     int cnt=0;
33     int len=0;
34     sort(v.begin(),v.end());
35     for(int i=0;i<int(v.size())-1;i++){
36         ans[cnt++]=mkp(v[i].S,v[i+1].S);
37         v[i].F--;
38         v[i+1].F--;
39         len++;
40     }
41     if(v1.size()>=2){
42         int p=2;
43         len+=2;
44         if(v.size()&&v[0].F){
45         v[0].F--;
46         ans[cnt++]=mkp(v[0].S,v1[0]);
47         }
48         
49         if(v.size()&&v[int(v.size())-1>=0?v.size()-1:0].F){
50             v[int(v.size())-1>=0?v.size()-1:0].F--;
51             ans[cnt++]=mkp(v[int(v.size())-1>=0?v.size()-1:0].S,v1[1]);
52         }
53     //    ans[cnt++]=mkp(v[0].S,v1[0]);
54         
55         for(int i=0;i<int(v.size());i++){
56             while(p<v1.size()&&v[i].F>0){
57                 ans[cnt++]=mkp(v[i].S,v1[p]);
58                 p++;
59                 v[i].F--;
60             }
61             if(p==v1.size())break;
62         }
63     }
64     else {
65 
66         if(v1.size()==1){
67             len+=1;
68             ans[cnt++]=mkp(v1[0],v[0].S);
69         }
70     }
71     //cout<<cnt<<endl;
72     if(cnt!=n-1){
73         cout<<"NO\n";
74         return 0;
75     }
76     cout<<"YES ";cout<<len<<endl;
77     cout<<cnt<<endl;
78     for(int i=0;i<cnt;i++){
79         cout<<ans[i].F<<" "<<ans[i].S<<endl;
80     }
81     return 0;    
82 }