题目描述

你需要构造一棵至少有两个顶点的树，树上的每条边有一个非负整数边权。树上两点 i,j 的距离dis(i,j) 定义为树上连接i 和j 这两点的简单路径上的边权和。

我们定义这棵树的直径为，所有满足 1≤i<j≤n 的  (i,j) 中， dis(i,j) 最大的。如果有多个这样的  (i,j)，那么均为直径。

你需要构造一个恰有 k 个直径的树。可以证明在给定的限制下一定有解。

你构造的树需要保证 2≤n≤5000，且每条边的边权满足 50≤w≤10^5。

对于所有数据，满足 1≤k≤5000000。

Solution

构造题真是有意思…[然而本蒟蒻不会x]

构造一棵挂了三个菊花的图…

大概长这样？

我图画的还是好丑啊

我们要干一件事情我们使得每个菊花图内的每一个分叉都能和另一个菊花的任意一个分叉形成一条直径

这时候我们设左边那棵菊花的节点数为a，下面那棵的节点数为b，右边那棵的节点数为c

那么这个图的直径的数量就是ab+bc+ac

然后我们感性理解打表一下发现，a,b,c最大为1500的时候，就可以做出K的所有情况。

我好菜啊都不会构造

Code

1. #include <bits/stdc++.h>  
2. using namespace std;  
3. int a,b,c,K;  
4. int main()  
5. {  
6.     freopen("diameter.in","r",stdin);  
7.     freopen("diameter.out","w",stdout);  
8.     scanf("%d",&K);  
9.     for (a=1;a<=1500;a++)  
10.       for (b=a;b<=1500;b++)  
11.         for (c=b;c<=1500;c++)  
12.           if (a*b*1ll+b*c*1ll+a*c*1ll==K)  
13.             goto sinian;  
14.     a=b=c=-2;  
15.     sinian:  
16.     if (a==-2||K<=2000)  
17.     {  
18.         printf("%d\n",K+1);  
19.         printf("1 2 2\n");  
20.         for (int i=2;i<=K;i++)  
21.           printf("%d %d 0\n",i,i+1);  
22.     }  
23.     else  
24.     {  
25.         printf("%d\n",a+b+c+1);  
26.         printf("1 2 6666\n");  
27.         printf("1 3 6666\n");  
28.         printf("1 4 6666\n");  
29.         --a;--b;--c;  
30.         for (int i=5;i<a+5;i++)  
31.           printf("2 %d 0\n",i);  
32.         for (int i=a+5;i<a+b+5;i++)  
33.           printf("3 %d 0\n",i);  
34.         for (int i=a+b+5;i<a+b+c+5;i++)  
35.           printf("4 %d 0\n",i);  
36.     }  
37.     return 0;  
38. }  

最新文章

1. Ubuntu配置OpenLDAP
2. Appium学习笔记（一）--安装与配置
3. RTC实时时钟
4. 【C】 02 - 程序结构和预处理
5. Leetcode: Insert Delete GetRandom O(1) - Duplicates allowed
6. jq向上无缝滚动
7. 图像编程学习笔记2——bmp位图平移
8. 通俗易懂的分析如何用Python实现一只小爬虫，爬取拉勾网的职位信息
9. 异步任务利器Celery(一)介绍
10. C语言的整型溢出问题 int、long、long long取值范围 最大最小值
11. JavaScript访问对象属性
12. 使用 rlist 包处理嵌套数据结构
13. 自动化运维工具 SaltStack 在云计算环境中的实践
14. 关于Javascript表单验证
15. IOS开发 Application Kit框架的线程安全
16. python之爬虫（二）爬虫的原理
17. mongodb分片集群（无副本集）搭建
18. ubantu忘记登录密码怎么办？（ubantu16.04）
19. 转帖 JS的基础语法2
20. June 10th 2017 Week 23rd Saturday

热门文章

1. 自学PHP的野方法
2. Java方法_数组
3. qt学习(二) buttong layout spinbox slider 示例
4. 静态HTML服务器
5. Markdown 手册
6. Python中ndarray数组切片问题a[-n -x:-y]
7. 3 python之基础概要
8. iOS&#39;s GCD Note
9. 数据挖掘分类算法之决策树（zz）
10. Web数据挖掘综述