QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#319268 | #7753. Energy Distribution | Djangle162857 | WA | 1ms | 4016kb | C++14 | 2.1kb | 2024-02-02 11:34:54 | 2024-02-02 11:34:55 |
Judging History
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'