ACM模版

描述

题解

给定一些路灯，想要关闭尽可能多的路灯，但是要保证前三个路灯是连着的（光线交合重叠），最简单的应该可以通过Floyd求任意两点间的连线，但是不知道会不会超时，麻烦一些的是跑三次spfa。

这里我要记录一个十分让我伤心的错误，提交了十几二十次才定位到了一个万万没想到的错误，第一次被这个地方坑，以致于查找bug时都没有把它当做嫌疑犯……

在写程序时我们经常用INF代表无穷大，而INF到底多大合适呢？对于大多数题，INF定位0x3f3f3f3f，为什么呢？因为这样在初始化数组时会十分便捷，用memset(cost, 0x3f, sizeof(cost))，这样一下子就全部初始化为INF了，并且这里考虑到了溢出问题，也就是说INF+INF时并不会溢出，因为很多题中一般需要防范INF+INF的情况出现，这也是一般不使用0x7f7f7f7f的缘故，可是，这道题，第一次在这个INF上坑了我，代码中出现了dist[0][i] + dist[1][i] + dist[2][i]，这也就构成了INF+INF+INF的可能，最终导致溢出，整整栽了一个多小时才找到问题所在，铭记吧~~~最后这里改成了0x1f1f1f1f就OK了……

代码

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int MAXN = 205;
const int INF = 0x1f1f1f1f;

struct node
{
    int x, y, r;
} light[MAXN];

int g[MAXN][MAXN];
int dist[3][MAXN];
int vis[MAXN];

// 判断两个灯是否相交
int judge(int i, int j)
{
    int x = light[i].x - light[j].x;
    int y = light[i].y - light[j].y;
    int d = x * x + y * y;
    int r = light[i].r + light[j].r;
    if (r * r >= d)
    {
        return 1;
    }
    return 0;
}

void spfa(int s, int n, int *dis)
{
    memset(vis, 0, sizeof(vis));

    for (int i = 0; i < n; i++)
    {
        dis[i] = INF;
    }
    dis[s] = 0;
    queue<int> q;
    q.push(s);
    vis[s] = 1;
    while (!q.empty())
    {
        s = q.front();
        q.pop();
        vis[s] = 0;
        for (int i = 0; i < n; i++)
        {
            if (dis[i] > dis[s] + g[s][i])
            {
                dis[i] = dis[s] + g[s][i];
                if (!vis[i])
                {
                    vis[i] = 1;
                    q.push(i);
                }
            }
        }
    }
}

int main()
{
    int T;
    scanf("%d", &T);

    int n;
    while (T--)
    {
        scanf("%d", &n);

        int x, y, r;
        for (int i = 0; i < n; i++)
        {
            scanf("%d%d%d", &x, &y, &r);
            light[i].x = x;
            light[i].y = y;
            light[i].r = r;
        }
        // 建无向图
        for (int i = 0; i < n; i++)
        {
            g[i][i] = 0;
            for (int j = 0; j < i; j++)
            {
                if (judge(i, j))
                {
                    g[i][j] = g[j][i] = 1;
                }
                else
                {
                    g[i][j] = g[j][i] = INF;
                }
            }
        }
        spfa(0, n, dist[0]);
        spfa(1, n, dist[1]);
        spfa(2, n, dist[2]);

        int ans = INF;
        for (int i = 0; i < n; i++)
        {
            ans = min(ans, dist[0][i] + dist[1][i] + dist[2][i]);
        }

        if (ans < INF)
        {
            printf("%d\n", n - ans - 1);
        }
        else
        {
            printf("-1\n");
        }
    }

    return 0;
}

参考

《最短路》