【CF】【图论】【思维】D. Maximum Diameter Graph
2021/9/15 23:35:49
本文主要是介绍【CF】【图论】【思维】D. Maximum Diameter Graph,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
D. Maximum Diameter Graph
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; }
这篇关于【CF】【图论】【思维】D. Maximum Diameter Graph的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01UniApp 中组件的生命周期是多少-icode9专业技术文章分享
- 2024-11-01如何使用Svg Sprite Icon简化网页图标管理
- 2024-10-31Excel数据导出课程:新手从入门到精通的实用教程
- 2024-10-31Excel数据导入课程:新手入门指南
- 2024-10-31RBAC的权限课程:新手入门教程
- 2024-10-31Svg Sprite Icon课程:新手入门必备指南
- 2024-10-31怎么配置 L2TP 允许多用户连接-icode9专业技术文章分享
- 2024-10-31怎么在FreeBSD上 安装 OpenResty-icode9专业技术文章分享
- 2024-10-31运行 modprobe l2tp_ppp 时收到“module not found”消息提醒是什么-icode9专业技术文章分享
- 2024-10-31FreeBSD的下载命令有哪些-icode9专业技术文章分享