爬山算法 70pts 求条
查看原帖
爬山算法 70pts 求条
764666
LostKeyToReach楼主2024/8/10 15:05
#include <bits/stdc++.h>
#define ll long long
#define int long long
#define debug(x) cerr << (#x) << '\n'
#define ls (u << 1)
#define rs (u << 1 | 1)
#define pii pair <int, int>
#define pb emplace_back
#define chkmin(x, y) x > y ? x = y : 0
#define chkmax(x, y) x < y ? x = y : 0
#define double long double
#define L(i, a, b) for (int i = (a); i <= (b); i++)
#define R(i, a, b) for (int i = (a); i >= (b); i--)
using namespace std;
const double eps = 1e-10;
const double dt = 0.999;
const int N = 1e5 + 6;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define rd(n) uniform_int_distribution <int>(1, n)(rnd)
#define rddb(n) uniform_real_distribution <double>(1, n)(rnd)
int n;
double p[14][14], sum[14], delta[14], dis[14], ans[14];
void SA() {
	double temp = 2000.0;
	for (; temp >= eps; temp *= dt) {
		double sum = 0;
		L(i, 1, n + 1) {
			dis[i] = delta[i] = 0.0;
			L(j, 1, n) {
				dis[i] += (ans[j] - p[i][j]) * (ans[j] - p[i][j]);
			}
			dis[i] = sqrt(dis[i]), sum += dis[i];
		}
		sum /= (1.0 * (n + 1));
		L(i, 1, n + 1) {
			L(j, 1, n) {
				delta[j] += (dis[i] - sum) * (p[i][j] - ans[j]) * 1.0 / sum;
			}
		}
		L(i, 1, n) {
			ans[i] += temp * delta[i];
		}
	}
}
signed main() {
	cin >> n;
	L(i, 1, n + 1) {
		L(j, 1, n) {
			cin >> p[i][j];
			sum[j] += p[i][j];
		}
//		sum[i] /= (1.0 * (n + 1));
	}
	L(i, 1, n) {
		sum[i] /= (1.0 * (n + 1));
	}
	while ((double)clock() / CLOCKS_PER_SEC < 0.99) SA();
	L(i, 1, n) {
		cout << fixed << setprecision(3) << ans[i] << ' ';
	}
}
2024/8/10 15:05
加载中...