P7639 [BalticOI 2006 Day 1] COUNTRIES

Rigel · 2024-05-22 18:04:03 · 题解

题意

在一个二维平面上有 n 个城市。其中，城市 i(i\in [1,n],i\in \mathbb{Z}) 的坐标为 (x_i,y_i)，兵力为 s_i。

定义城市 j 对城市 i 的威胁值 t=\displaystyle{\frac{s_j}{(x_i-x_j)^2+(y_i-y_j)^2}}，若 t>s_i，则称城市 i 被城市 j 威胁 (i \neq j)。

一个城市的性质有以下三种可能：

一个王国的首都。这个城市不受任何城市的威胁。
一个民主国家的首都。这个城市受到多个城市的威胁，且有多个城市对这个城市的威胁值与这个城市所受最大威胁值相等。
服从于另一个作为首都的城市。这个城市受到多个城市的威胁，且这些城市中有且仅有一个对它威胁值最大的城市 id，那么这个城市将服从于城市 id 或城市 id 所服从的首都。

请给出每一个城市的性质。

思路

对于每一个城市，枚举所有城市，找到所有能对其产生威胁的城市。记录这个城市所受最大威胁值 mx、产生最大威胁值的城市编号 id、产生最大威胁值的城市个数 cnt。

当 cnt=0 时，表示这个城市不受任何城市威胁，这个城市为王国的首都。
当 cnt=1 时，表示这个城市服从于城市 id（对它的威胁值为 mx）。当出现这种情况时，可使用并查集维护城市之间的服从关系。
当 cnt\geq 2 时，表示这个城市同时受多个威胁值为 mx 的城市威胁，这个城市为民主国家的首都。

时间复杂度为 \mathcal{O}(n^2)，对于 n\leq 10^3 可以实现。

代码实现

1. 城市信息存储

可以使用结构体存储。

struct node{
    int x,y,s,fa,f;
}a[maxn];

其中，x，y 分别表示城市的横纵坐标，s 表示城市的兵力，fa 表示这个城市服从的城市（若为自己则表示这个城市为首都）。若这个城市为首都，则 f 存储这个首都的类型（1 和 2 分别代表王国的首都和民主国家的首都），否则为 0。

2. 城市对其他城市的威胁值计算

计算城市 i 与城市 j 的距离：

double dis(int i,int j){
    return (double)((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y));
}

于是我们得到城市 j 对城市 i 的威胁值：

t=(double)a[j].s/dis(i,j); // 城市 j 的兵力除以距离的平方

注意这里应该用 double 类型存储威胁值，因为它不一定是一个整数。

3. 城市性质的判断

当获得城市 i 受到城市 j 的威胁值 t 之后，首先要判断 t 与 s_i 的关系。若 t\leq s_i，直接跳过城市 j；否则，应判断 t 与城市 i 所受的最大威胁值 mx 是否相等。若相等，则最大威胁值个数 cnt\gets cnt+1；否则更新最大威胁值 mx、产生最大威胁值的城市编号 id、产生最大威胁值的城市个数 cnt（赋值为 1）。

由于威胁值用浮点数存储，会产生精度问题。我们需要加一个判断浮点数是否相等的函数。

bool check(double x,double y){
    if(_abs(x-y)<=1e-10)return 1; // 若两个浮点数的误差小于一定值，则认为这两个浮点数是相等的
    return 0;
}

在得到 mx、id 与 cnt 之后，根据 cnt 的值即可判断城市 i 的性质。当 cnt=1 时，应找到城市 id 所服从的城市，并令城市 i 也服从于这个城市。

int getfa(int x){
    return (a[x].fa==x)?x:(a[x].fa=getfa(a[x].fa)); // 并查集
}

for(int i=1;i<=n;i++){
    int id=0,cnt=0; // 产生最大威胁值的城市编号、产生最大威胁值的城市个数
    double mx=0; // 城市 i 所受最大威胁值
    for(int j=1;j<=n;j++){
        if(i==j)continue;
        double t=(double)a[j].s/dis(i,j); // 计算 j 对 i 的威胁值
        if(t<(double)a[i].s||check(t,(double)a[i].s))continue; // 若 t < a[i].s 或 t == a[i].s ，跳过
        if(t>mx&&!check(mx,t))mx=t,id=j,cnt=1; // 若 t > 当前城市 i 所受最大威胁值 mx ，则更新 mx 、 id 与 cnt
        else if(check(t,mx))cnt++; // 若 t == mx ，产生最大威胁值的城市个数加一
    }
    if(!cnt)a[i].f=1; // 城市 i 为王国的首都
    if(cnt>1)a[i].f=2; // 城市 i 为民主国家的首都
    if(cnt==1)a[i].fa=getfa(id); // 城市 i 服从于城市 id
}

在此之后，还需要进行：

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

这样可以保证找到每个城市服从的首都。

完整代码

#include<bits/stdc++.h>
#define int long long
#define _abs(x) ((x)>0?(x):(-(x)))
#define maxn 1010
using namespace std;
int n;
struct node{
    int x,y,s,fa,f;
}a[maxn];
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')ret=ret*10+(ch&15),ch=getchar();
    return ret*f;
}
double dis(int i,int j){
    return (double)((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y));
}
bool check(double x,double y){
    if(_abs(x-y)<=1e-10)return 1;
    return 0;
}
int getfa(int x){
    return (a[x].fa==x)?x:(a[x].fa=getfa(a[x].fa));
}
signed main(){
    n=read();
    for(int i=1;i<=n;i++)a[i].x=read(),a[i].y=read(),a[i].s=read(),a[i].fa=i;
    for(int i=1;i<=n;i++){
        int id=0,cnt=0;
        double mx=0;
        for(int j=1;j<=n;j++){
            if(i==j)continue;
            double t=(double)a[j].s/dis(i,j);
            if(t<(double)a[i].s||check(t,(double)a[i].s))continue;
            if(t>mx&&!check(mx,t))mx=t,id=j,cnt=1;
            else if(check(t,mx))cnt++;
        }
        if(!cnt)a[i].f=1;
        if(cnt>1)a[i].f=2;
        if(cnt==1)a[i].fa=getfa(id);
    }
    for(int i=1;i<=n;i++)getfa(i);
    for(int i=1;i<=n;i++){
        if(a[i].fa==i)printf("%c\n",(a[i].f==1)?'K':'D');
        else printf("%lld\n",a[i].fa);
    }
    return 0;
}