Maximum Diameter Graph CodeForces - 1082D

本文主要是介绍Maximum Diameter Graph CodeForces - 1082D，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://codeforces.com/contest/1082/problem/D

先判度数列之和是否大于等于2*n-2 小于则构不成图

然后就是构造直径最长的树 度数大于1的当树干 先连起来 度数为1的只能当叶子 一个一个补到树干上即可

我tm智障啊 加叶节点时忘记先加到端点上了 很烦

 

 

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int maxn=5e2+10;struct node
{int u,v;
};vector <int> pre1,pre2;
node ans[maxn];
int a[maxn];
int n,tot;int main()
{int i,j,sum,cnt,flag;scanf("%d",&n);sum=0,cnt=0;for(i=1;i<=n;i++){scanf("%d",&a[i]);sum+=a[i];if(a[i]==1){pre1.pb(i);cnt++;}else pre2.pb(i);}if(sum<2*n-2) printf("NO\n");else{for(i=0;i+1<pre2.size();i++){tot++;ans[tot].u=pre2[i],ans[tot].v=pre2[i+1];a[pre2[i]]--,a[pre2[i+1]]--;}if(pre1.size()>=1){tot++;ans[tot].u=pre1[0],ans[tot].v=pre2[0];a[pre1[0]]--,a[pre2[0]]--;}if(pre1.size()>=2){tot++;ans[tot].u=pre1[1],ans[tot].v=pre2[pre2.size()-1];a[pre1[1]]--,a[pre2[pre2.size()-1]]--;}for(i=2;i<pre1.size();i++){for(j=0;j<pre2.size();j++){if(a[pre2[j]]>0){tot++;ans[tot].u=pre1[i],ans[tot].v=pre2[j];a[pre1[i]]--,a[pre2[j]]--;break;}}}if(cnt>2) printf("YES %d\n",n-1-(cnt-2));else printf("YES %d\n",n-1);printf("%d\n",tot);for(i=1;i<=tot;i++) printf("%d %d\n",ans[i].u,ans[i].v);}return 0;
}

 

这篇关于Maximum Diameter Graph CodeForces - 1082D的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---