2021“MINIEYE杯”中国大学生算法设计超级联赛（8）Ink on paper 最小生成树

😊 | Powered By HeartFireY

Problem Description

题目大意：几个油滴滴在纸上，以 0.5 c m / s 0.5cm/s 0.5cm/s的速度环形扩散，求所有油滴从滴到纸上开始计时，扩散到全部接触时的时间。

画个图，立马就明白在干啥了：

如果使所有圆环合为如上图所示的接触状态，且每个圆环扩散的速度相同，那么每两个距离最近的圆环必定最先接触，也就是在求起始原点的最小生成树。而要使圆环合并到一滩油滴(感性理解…)所需的时间，就是在求最小生成树上最长边的一半长度除以 0.5 c m / s 0.5 cm/s 0.5cm/s​，也就是最长边的长度。而最终结果又是平方形式，那么两点间距离的根号也可以直接拿掉了。任意两点 ( x 1 , y 1 ) ( x 2 , y 2 ) (x_1,y_1)(x_2, y_2) (x1​,y1​)(x2​,y2​)间的距离我们可以采用 ( x 2 − x 1 ) 2 + ( y 2 − y 1 ) 2 (x_2 - x_1)^2+(y_2 - y_1)^2 (x2​−x1​)2+(y2​−y1​)2来表示。那么剩下的就是直接跑最小生成树即可。

注意，这里由于是稠密图，因此 P r i m Prim Prim算法更适合本题。 K r u s k a l Kruskal Kruskal听说…会被卡掉…​

Accepted Code

#include 
#define int long long
using namespace std;

const int N = 5000 + 10, INF = 9e18;
int g[N][N], d[N], n, x[N], y[N];
bool vis[N];

inline int getdis(int x1, int y1, int x2, int y2){ return (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1); }

inline void solve(){
    cin >> n;
    for(int i = 1; i > x[i] >> y[i];
    for(int i = 1; i