1 条题解
-
0
题意分析
题目要求将一个仙人掌图(每个边最多属于一个简单环的连通无向图)划分为个大小相等的连通子图。每个子图需包含个顶点,且顶点编号按升序输出。输入保证能被整除,且图是仙人掌图。需判断是否存在合法划分,若存在则输出各子图顶点,否则输出-1。
解题思路
根据输入路径解析边,用邻接表存储图,同时标记环和桥的结构。利用仙人掌图特性(环和桥的组合),通过DFS或BFS遍历子图,确保每个子图连通且包含个顶点。从任意顶点出发,尝试扩展子图至个顶点,且保持连通。若遍历中无法找到足够顶点或子图不连通,则判定无解。每个子图顶点排序后输出,若无法划分则输出-1。
#include<cstdio> #include<stack> #include<cmath> #include<iostream> #include<algorithm> using namespace std; struct Point { double x, y, z; }p[10010]; int n; double dis(Point a, Point b) { return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); } double cla(double r) { double h = 0; for (int i = 0; i < n; i++) { h = max(h, p[i].z * r / (r - dis(p[i], p[n]))); } return h; } int main() { while (cin >> n) { p[n].x = p[n].y = p[n].z = 0; //把p[n]设为原点 double l = 0, r = 10010, mid, m; double H, R; for (int i = 0; i < n; i++) { scanf("%lf%lf%lf", &p[i].x, &p[i].y, &p[i].z); l = max(l, dis(p[i], p[n])); } while (r - l > 1e-7) //三分 { mid = (r + l) / 2; m = (mid + r) / 2; double h1 = cla(mid); //利用相似三角形求高h double h2 = cla(m); if (mid * mid * h1 < m * m * h2) { r = m; H = h1, R = mid; } else { l = mid; H = h2, R = m; } } printf("%0.3f %0.3f\n", H, R); //G++用%lf提交会WA!!! } return 0; }
- 1
信息
- ID
- 2943
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者