HDU 3832 Earth Hour（最短路）

题目地址：HDU 3832

这个题的这个方法我无法给出证明。我当时这个灵感出来的时候是想的是要想覆盖的点最少，那就要尽量重复利用这些点，然后要有两个之间是通过另一个点间接连接的，这样会充分利用那些点。然后就这样写了一次，一直WA。。然后中午睡觉的时候突然想到了有一种情况这样做是不对的。那就是有个点作为中间点，与三个点相连的情况，这种情况虽然也符合，但是会有重复边。。。但是恰恰相反。。重复边应该越多越好。。那就充分利用了这些点。那么这个点应该怎么找呢？那就直接枚举好了。但是枚举每个点都求一次最短路的话很明显不科学。。反正只是利用到那三个点的最短距离，那就只对这三个点分别求一次，那别的点到这三个点的最短路就都求出来了。然后枚举所有点到三个点的距离之和，找出最小的。再用n减去最小值就是需要关闭的最大值了。

代码如下：

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
int head[300], cnt, vis[300];
int d[3][301];
struct node1
{
    int x, y, r;
} dian[1000000];
struct node
{
    int u, v, w, next;
} edge[1000000];
void add(int u, int v, int w)
{
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
void spfa(int source, int x)
{
    memset(d[x],INF,sizeof(d[x]));
    memset(vis,0,sizeof(vis));
    d[x][source]=0;
    deque<int>q;
    q.push_back(source);
    while(!q.empty())
    {
        int u=q.front();
        q.pop_front();
        vis[u]=0;
        for(int i=head[u]; i!=-1; i=edge[i].next)
        {
            int v=edge[i].v;
            if(d[x][v]>d[x][u]+edge[i].w)
            {
                d[x][v]=d[x][u]+edge[i].w;
                if(!vis[v])
                {
                    vis[v]=1;
                    if(!q.empty()&&d[x][v]<d[x][q.front()])
                    {
                        q.push_front(v);
                    }
                    else
                    {
                        q.push_back(v);
                    }
                }
            }
        }
    }
}
int main()
{
    int t, n, x, y, r, ans, i, j, min1;
    double z;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        memset(head,-1,sizeof(head));
        cnt=0;
        for(i=1; i<=n; i++)
        {
            scanf("%d%d%d",&dian[i].x,&dian[i].y,&dian[i].r);
        }
        for(i=1; i<=n; i++)
        {
            for(j=1; j<i; j++)
            {
                z=sqrt((dian[i].x-dian[j].x)*1.0*(dian[i].x-dian[j].x)+(dian[i].y-dian[j].y)*1.0*(dian[i].y-dian[j].y));
                if(z<=dian[i].r+dian[j].r)
                {
                    add(i,j,1);
                    add(j,i,1);
                }
            }
        }
        spfa(1,0);
        spfa(2,1);
        spfa(3,2);
        min1=INF;
        if(d[0][2]==INF||d[0][3]==INF)
        {
            printf("-1\n");
            continue ;
        }
        for(i=1;i<=n;i++)
        {
            if(d[0][i]!=INF&&d[1][i]!=INF&&d[2][i]!=INF)
            {
                if(min1>d[0][i]+d[1][i]+d[2][i]+1)
                {
                    min1=d[0][i]+d[1][i]+d[2][i]+1;
                }
            }
        }
        printf("%d\n",n-min1);
    }
    return 0;
}

HDU 3832 Earth Hour（最短路）,布布扣,bubuko.com

HDU 3832 Earth Hour（最短路）

原文：http://blog.csdn.net/scf0920/article/details/38337347