Codeforces Round #306 (Div. 2) D
2 seconds
256 megabytes
standard input
standard output
An undirected graph is called k-regular, if the degrees of all its vertices are equal k. An edge of a connected graph is called a bridge, if after removing it the graph is being split into two connected components.
Build a connected undirected k-regular graph containing at least one bridge, or else state that such graph doesn't exist.
The single line of the input contains integer k (1 ≤ k ≤ 100) — the required degree of the vertices of the regular graph.
Print "NO" (without quotes), if such graph doesn't exist.
Otherwise, print "YES" in the first line and the description of any suitable graph in the next lines.
The description of the made graph must start with numbers n and m — the number of vertices and edges respectively.
Each of the next m lines must contain two integers, a and b (1 ≤ a, b ≤ n, a ≠ b), that mean that there is an edge connecting the vertices a and b. A graph shouldn't contain multiple edges and edges that lead from a vertex to itself. A graph must be connected, the degrees of all vertices of the graph must be equal k. At least one edge of the graph must be a bridge. You can print the edges of the graph in any order. You can print the ends of each edge in any order.
The constructed graph must contain at most 106 vertices and 106 edges (it is guaranteed that if at least one graph that meets the requirements exists, then there also exists the graph with at most 106 vertices and at most 106 edges).
1
YES
2 1
1 2
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <utility>
using namespace std; struct edge{
int u,v;
edge(){}
edge(int uu,int vv){u=uu,v=vv;}
}; vector<edge>ans; int main(){
int k;
while(scanf("%d",&k)!=EOF){
if(k%2==0){
puts("NO");
}
else{
if(k==1){
puts("YES");
printf("%d %d\n",2,1);
printf("%d %d\n",1,2);
continue;
}
ans.clear();
k+=2;
int g=k/2;
for(int i=0;i<k-1;i++){
for(int j=1;j<g;j++){
ans.push_back(edge(i,(i+j)%(k-1)));
ans.push_back(edge(i+k,(i+j)%(k-1)+k));
}
}
for(int i=1;i<k-1;i++){
ans.push_back(edge(i,k-1));
ans.push_back(edge(i+k,(k-1)+k));
}
ans.push_back(edge(0,k));
puts("YES");
int sz=ans.size();
printf("%d %d\n",k*2,sz);
for(int i=0;i<sz;i++){
printf("%d %d\n",ans[i].u+1,ans[i].v+1);
} }
}
return 0;
}
最新文章
- DataList 用法详解
- spring AOP 的几种实现方式(能测试)
- DrawerLayout的使用
- invalid END header (bad central directory offset) 异常解决方法
- Struts2框架的运行流程
- MultiTouch camera controls source code
- javascript Window对象 第16节
- python3.4.2 安装Pillow
- Java-NIO(三):直接缓冲区与非直接缓冲区
- android拍照获得图片及获得图片后剪切设置到ImageView
- 小小知识点(八)——星座图与PSK、QAM调制的关系
- 分布式锁与实现(一)——基于Redis实现 【比较靠谱】
- loadrunner 参数化取值方式详解
- react组件通信那些事儿
- [UE4]世界坐标和相对坐标
- 【电信我想问一下,网页上多出的隐藏广告】究竟谁在耍流氓,还要不要脸了??? 0817tt 植入广告
- 【2014年12月6日】HR交流会
- druid.io本地集群搭建 / 扩展集群搭建
- 列表生成式&;生成器表达式
- LINQ教程二:LINQ操作语法
热门文章
- 【BZOJ2762】[JLOI2011]不等式组(树状数组)
- ACM_填格子
- 关于static函数在类中的定义和使用
- SQL基本操作——row_number() over()
- Java_Web三大框架之Hibernate+jsp+HQL分页查询
- python_文件io
- 关于在win7旗舰版32位上 安装 net4.0 的闪退问题研究 和安装sqlserver2008问题
- JVM 内存设置大小(Xms Xmx PermSize MaxPermSize 区别)
- Python 之re正则表达式
- windows环境安装python虚拟环境