QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#319268#7753. Energy DistributionDjangle162857WA 1ms4016kbC++142.1kb2024-02-02 11:34:542024-02-02 11:34:55

Judging History

你现在查看的是最新测评结果

  • [2024-10-31 10:22:30]
  • hack成功,自动添加数据
  • (/hack/1089)
  • [2024-02-02 11:34:55]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4016kb
  • [2024-02-02 11:34:54]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << #x << " == " << x << endl
#define el '\n'
typedef long long ll;
const int mod = 1000000007;
const int inf = 2147483647;
const int N = 200020;
double w[20][20];
int n;
const double eps = 1e-8;
double getans(vector<int> a) {
	vector<int> x(n + 5);
	vector<vector<double>> g(n + 5);
	for (int i = 0; i <= n + 4; i++) {
		g[i].resize(n + 5);
	}
	int tmp = 0;
	for (int i = 1; i <= n; i++) {
		if (a[i] == 1)
			x[++tmp] = i;
	}
	for (int i = 1; i <= tmp; i++) {
		for (int j = 1; j <= tmp; j++) {
			g[i][j] = w[x[i]][x[j]];
		}
		g[i][tmp + 1] = -1;
		g[i][tmp + 2] = 0;
	}
	for (int i = 1; i <= tmp; i++) {
		g[tmp + 1][i] = 1;
	}
	g[tmp + 1][tmp + 2] = 1;
	int m = tmp + 1;
	for (int i = 1; i <= m; i++) {
		int mx = i;
		for (int j = i + 1; j <= m; j++) {
			if (fabs(g[j][i]) > fabs(g[mx][i])) {
				mx = j;
			}
		}
		for (int j = 1; j <= m + 1; j++) {
			swap(g[i][j], g[mx][j]);
		}
		if (fabs(g[i][i]) < eps) {
			return 0;
		}
		for (int j = m + 1; j >= 1; j--) {
			g[i][j] = g[i][j] / g[i][i];
		}
		for (int j = 1; j <= m; j++) {
			if (j != i) {
				double temp = g[j][i] / g[i][i];
				for (int k = 1; k <= m + 1; k++) {
					g[j][k] -= g[i][k] * temp;
				}
			}
		}
	}
	vector<double> ans(n + 5);
	for (int i = 1; i <= tmp; i++) {
		ans[x[i]] = g[i][m + 1];
	}
	double res = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			res += ans[i] * ans[j] * w[i][j];
		}
	}
	return res;
}
void solve() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> w[i][j];
		}
	}
	double ans = 0.00;
	for (int s = 0; s < (1 << n); s++) {
		vector<int> a(n + 1);
		for (int j = 1; j <= n; j++) {
			int now = (1 << (j - 1));
			if (s & now)
				a[j] = 0;
			else
				a[j] = 1;
		}
		double res = getans(a);
		ans = max(ans, res);
	}
	cout << ans << endl;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int T = 1;
	// cin>>T;
	while (T--) {
		solve();
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3784kb

input:

2
0 1
1 0

output:

0.25

result:

ok found '0.2500000', expected '0.2500000', error '0.0000000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 4016kb

input:

3
0 2 1
2 0 2
1 2 0

output:

0.571429

result:

ok found '0.5714290', expected '0.5714290', error '0.0000000'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3868kb

input:

3
0 1 2
1 0 1
2 1 0

output:

0.5

result:

ok found '0.5000000', expected '0.5000000', error '0.0000000'

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3896kb

input:

4
0 3 1 0
3 0 1 0
1 1 0 2
0 0 2 0

output:

1

result:

wrong answer 1st numbers differ - expected: '0.7500000', found: '1.0000000', error = '0.2500000'