1 条题解

  • 0
    @ 2025-6-10 21:20:45

    题意分析

    题目要求将一个仙人掌图(每个边最多属于一个简单环的连通无向图)划分为kk个大小相等的连通子图。每个子图需包含n/kn/k个顶点,且顶点编号按升序输出。输入保证nn能被kk整除,且图是仙人掌图。需判断是否存在合法划分,若存在则输出各子图顶点,否则输出-1。

    解题思路

    根据输入路径解析边,用邻接表存储图,同时标记环和桥的结构。利用仙人掌图特性(环和桥的组合),通过DFS或BFS遍历子图,确保每个子图连通且包含n/kn/k个顶点。从任意顶点出发,尝试扩展子图至n/kn/k个顶点,且保持连通。若遍历中无法找到足够顶点或子图不连通,则判定无解。每个子图顶点排序后输出,若无法划分则输出-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
    上传者