hdoj 3832 Earth Hour（最短路）

￡神魔★判官ぃ 2022-08-26 12:12 17阅读 0赞

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3832

题意：给出n个半径和圆心坐标已知的点，编号为1 -- n ，求连接1 ，2 , 3所需要的最少圆。

题目的难点在于转化，转化为枚举其他点到当前 3 个点的最小距离。即最短路径、

分析：给出的是圆的坐标，首先我们知道，如果一个圆和其他所有圆都没有交集，那么这个圆肯定不能连通其他圆，先排除这些，然后求剩下有交集的圆连通1,2,3,所需要最少的

圆，那么我们以圆的编号为点，任意两个有交集的圆建立一条长度为 1 的边，我们是不是就转化为求1,2,3三个点间的最短路，而求三个点间的最短路，我们可以画图试试是不是要

通过一个中间点求得的路径是最短的，那么问题得到了解决。

求最短路有很多算法，这个题目都可以，这里给出spfs实现：

代码：

#include <cstdio>
    #include <vector>
    #include <iostream>
    #include <stack>
    #include <cstdio>
    #include <string>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    #include <queue>
    using namespace std;
    const int inf = 0x3f3f3f3f;
    const int N = 300;
    struct Point
    {
        int x,y;
        int r;
        int num;
    };
    Point a[N];
    struct Node
    {
        int v,len;
    };
    vector<Node> map[N];
    int n;
    void spfa(int s,int dis[])
    {
        int i;
        queue<int> q;
        for(i=0; i<N; i++)
            dis[i]=inf;
        dis[s]=0;
        q.push(s);
        while(!q.empty())
        {
            int u=q.front();
            q.pop();
            for(i=0; i<map[u].size(); i++)
            {
                Node p=map[u][i];
                if(dis[p.v]>dis[u]+p.len)
                {
                    dis[p.v]=dis[u]+p.len;
                    q.push(p.v);
                }
            }
        }
    }
    int main()
    {
        int dis1[N],dis2[N],dis3[N];
        int T;
        scanf("%d",&T);
        while(T--)
        {
            for(int i=0;i<N;i++)
                map[i].clear();
            scanf("%d",&n);
            memset(map,0,sizeof(map));
            for(int i=0; i<n; i++)
            {
                scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].r);
            }
            for(int i=0;i<n;i++)
            {
                for(int j=i+1;j<n;j++)
                {
                    int dist1=(a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y);
                    int dist2=(a[i].r+a[j].r)*(a[i].r+a[j].r);
                    if(dist1<=dist2)
                    {
                        Node p;
                        p.v=j;
                        p.len=1;
                        map[i].push_back(p);
                        p.v=i;
                        map[j].push_back(p);
                    }
                }
            }
            spfa(0,dis1);
            spfa(1,dis2);
            spfa(2,dis3);
            int ans=-1;
            for(int i=0;i<n;i++)
            {
                if(dis1[i]<inf&&dis2[i]<inf&&dis3[i]<inf)
                    ans=max(ans,n-(dis1[i]+dis2[i]+dis3[i]+1));
            }
            if(ans==inf)
                ans=-1;
            printf("%d\n",ans);
        }
        return 0;
    }