noip模拟赛 radius

分析：这道题实在是不好想，一个可以骗分的想法是假定要求的那个点在中心点上,可以骗得不少分.但是在边上的点要怎么确定呢？理论复杂度O(﹢无穷).答案一定是和端点有关的，涉及到最大值最小，考虑二分最大值，关键就是怎么check.如果有一条边x,还有一个点y,把y到x上的点的距离>mid的点给标记上，这样就会形成许多个区间，判断一下x是否被这些区间给完全覆盖住了，如果没有被完全覆盖住，证明这个最大值可以更小.思路非常奇妙,具体实现细节可以参看代码:

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn = , maxm = ;

int n, m, a[maxn][maxn], head[maxn], to[maxm],ans,len,top,nextt[maxm],w[maxm], tot = ;

struct node

{

    int x, y, z;

}e[];

struct node2

{

    int first, second;

}e2[];

void add(int x, int y, int z)

{

    w[tot] = z;

    to[tot] = y;

    nextt[tot] = head[x];

    head[x] = tot++;

}

void floyd()

{

    for (int k = ; k <= n; k++)

        for (int i = ; i <= n; i++)

            for (int j = ; j <= n; j++)

                if (a[i][j] > a[i][k] + a[k][j])

                    a[i][j] = a[i][k] + a[k][j];

}

void add2(int x, int y)

{

    e2[++top].first = x;

    e2[top].second = y;

}

bool cmp(node2 a, node2 b)

{

    if (a.first == b.first)

        return a.second < b.second;

    return a.first < b.first;

}

bool can()

{

    int x = ;

    sort(e2 + , e2 +  + top,cmp);

    for (int i = ; i <= top; i++)

    {

        if (x < e2[i].first)

            return false;

        if (x > e2[i].second)

            continue;

        x = e2[i].second + ;

    }

    if (x > len)

        return true;

    return false;

}

bool check(int p)

{

    bool flag = false;

    for (int i = ; i <= m; i++)

    {

        top = ;

        len = e[i].z;

        for (int j = ; j <= n; j++)

        {

            int x = p - a[e[i].x][j];

            int y = p - a[e[i].y][j];

            if (x <  && y < )

            {

                add2(, e[i].z);

                break;

            }

            if (x >= e[i].z || y >= e[i].z)

                continue;

            if (x + y >= e[i].z)

                continue;

            add2(max(, x + ), min(e[i].z, e[i].z - y - ));

        }

        if (!can())

            flag = ;

        if (flag)

            break;

    }

    if (flag)

        return true;

    return false;

}

int main()

{

    memset(a,  / , sizeof(a));

    scanf("%d%d", &n, &m);

    for (int i = ; i <= m; i++)

    {

        int u, v, z;

        scanf("%d%d%d", &u, &v, &z);

        z *= ;

        add(u, v, z);

        add(v, u, z);

        e[i].x = u;

        e[i].y = v;

        e[i].z = z;

        a[u][v] = a[v][u] = min(a[u][v], z);

    }

    for (int i = ; i <= n; i++)

        a[i][i] = ;

    floyd();

    int l = , r = ;

    while (l <= r)

    {

        int mid = (l + r) >> ;

        if (check(mid))

        {

            ans = mid;

            r = mid - ;

        }

        else

            l = mid + ;

    }

    double temp = ans / 2.0;

    printf("%.2lf\n", temp);

return ;

}

巴特西

noip模拟赛 radius

最新文章

热门文章