自动搬运

查看原文

来自洛谷，原作者为

	Rigel 苍山负雪，明烛天南。|| 高二现役 OIer。

搬运于2025-08-24 22:31:47，当前版本为作者最后更新于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)$。

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

1. 一个王国的首都。这个城市不受任何城市的威胁。

2. 一个民主国家的首都。这个城市受到多个城市的威胁，且有多个城市对这个城市的威胁值与这个城市所受最大威胁值相等。

3. 服从于另一个作为首都的城市。这个城市受到多个城市的威胁，且这些城市中有且仅有一个对它威胁值最大的城市 $id$，那么这个城市将服从于城市 $id$ 或城市 $id$ 所服从的首都。

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

思路

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

1. 当 $cnt=0$ 时，表示这个城市不受任何城市威胁，这个城市为王国的首都。

2. 当 $cnt=1$ 时，表示这个城市服从于城市 $id$（对它的威胁值为 $mx$）。当出现这种情况时，可使用并查集维护城市之间的服从关系。

3. 当 $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;
}