codeforces #550D Regular Bridge 构造
2024-08-26 00:37:54
题目大意:给定k(1≤k≤100),要求构造一张简单无向连通图,使得存在一个桥,且每一个点的度数都为k
k为偶数时无解
证明:
将这个图缩边双,能够得到一棵树
那么一定存在一个叶节点,仅仅连接一条桥边
那么这个边双内部全部点度数之和为偶数 除掉连出去的桥边外度数之和为奇数 故不合法
然后k为奇数的时候我们仅仅须要构造两个对称的边双被一条桥边连接的图即可了
因为每一个点度数为k。因此每一边至少须要k+1个点
可是k+1个点奇偶性不合法。因此每一边至少须要k+2个点
如今问题转化成了给定一个度数数组要求构造一张原图
这个在Wc2015讲过 每次找剩余的度数最大的点
如果这个点的度数为d 那么仅仅须要向其他度数最大的d个点连边即可
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 110
using namespace std;
struct edge{
int x,y;
edge() {}
edge(int _,int __):
x(_),y(__) {}
}stack[10100];
int k,top;
int degree[M],a[M];
bool Compare(int x,int y)
{
return degree[x] > degree[y] ;
}
int main()
{
int i,j;
cin>>k;
if(~k&1)
return puts("NO"),0;
puts("YES");
if(k==1)
return puts("2 1\n1 2"),0;
cout<<(k+2<<1)<<' '<<((k+2)*k)<<endl;
int n=k+2;
for(degree[1]=k-1,i=2;i<=n;i++)
degree[i]=k;
for(i=1;i<=n;i++)
a[i]=i;
for(i=1;i<=n;i++)
{
sort(a+1,a+n+1,Compare);
for(j=2;j<=degree[a[1]]+1;j++)
{
stack[++top]=edge(a[1],a[j]);
degree[a[j]]--;
}
degree[a[1]]=0;
}
for(i=1;i<=top;i++)
{
printf("%d %d\n",edges[i].x,edges[i].y);
printf("%d %d\n",edges[i].x+n,edges[i].y+n);
}
printf("%d\n",1,n+1);
return 0;
}
最新文章
- Delphi_03_Delphi_Object_Pascal_基本语法_01
- 使用sql语句创建修改SQL Server标识列(即自动增长列)
- eclipes的Spring注解SequenceGenerator(name=";sequenceGenerator";)报错的解决方式
- Android应用权限管理总结
- centos 虚拟机安装过程
- Scrum 体验活动笔记
- Serializable在C#中的作用.net中的对象序列化 (转)
- OSSEC集合
- 【转】【可用】Android 登录判断器,登录成功后帮你准确跳转到目标activity
- Grant的时候报错的解决:Access denied for user &;#39;root&;#39;@&;#39;localhost&;#39; (using password: YES)
- OCP-1Z0-051-标题决心-文章5称号
- adb 安装apk 报错:Failure [INSTALL_FAILED_CPU_ABI_INCOMPATIBLE]
- 中介者模式(Mediator)
- java中过多if-else分支语句的优化方案
- 20181207_Second_小结
- 路飞学城-Python开发集训-第3章
- 例:判断是不是自有属性hasOwnProperty方法
- flask 的session
- Vim编程常用命令
- [POJ2625][UVA10288]Coupons
热门文章
- 虚拟机Visualbox安装Ubuntu Server
- MySQL 使用硬链接配合truncate 删除2.2T的表
- 多表联合查询,利用 concat 模糊搜索
- python 连接数据库练习
- 【枚举】【权值分块】bzoj1112 [POI2008]砖块Klo
- [Gym101194G][CHINA-Final2016]Pandaria
- [JOISC2014]JOIOJI
- 1.6(学习笔记)EL表达式
- Bootstrap-datetimepicker日期插件简单使用
- Problem A: 调用函数,计算分段函数的值