题目链接

问题分析

随后系统的势能应当最低，即

\[ \sum w_i \times \sqrt{(x-x_i)^2+(y-y_i)^2} \]

最小。直接模拟退火。

参考程序 #include <cstdio> #include <ctime> #include <cstdlib> #include <cmath> #define Maxn 1010 int n, x[Maxn], y[Maxn], w[Maxn]; double X, Y, Cost, AnsX, AnsY, AnsC; inline double Rand() { return (double)rand() / RAND_MAX; } inline double Calc(double X, double Y) { double Ans = 0; for (int i = 1; i <= n; ++i) Ans += sqrt((x[i] - X) * (x[i] - X) + (y[i] - Y) * (y[i] - Y)) * w[i]; if (Ans < AnsC) AnsX = X, AnsY = Y, AnsC = Ans; return Ans; } int main() { srand(time(NULL)); scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d%d%d", &x[i], &y[i], &w[i]); for (int i = 1; i <= n; ++i) AnsX += x[i], AnsY += y[i]; AnsX = X = AnsX / n; AnsY = Y = AnsY / n; Cost = AnsC = Calc(X, Y); double T = 10000; while (T > 0.001) { double XX = X + T * (Rand() * 2 - 1); double YY = Y + T * (Rand() * 2 - 1); double C = Calc(XX, YY); if (exp((Cost - C) / T) > Rand()) X = XX, Y = YY, Cost = C; T *= 0.999; } for (int i = 1; i <= 1000; ++i) { //再来一点随机扰动 double XX = AnsX + T * (Rand() * 2 - 1); double YY = AnsY + T * (Rand() * 2 - 1); Calc(XX, YY); } printf("%.3lf %.3lf\n", AnsX, AnsY); return 0; }

[JSOI2004]平衡点 / 吊打XXX

标签：

原文地址：https://www.cnblogs.com/chy-2003/p/12028784.html

，