QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#395145#7753. Energy Distributionucup-team3215RE 0ms3984kbC++233.8kb2024-04-21 07:34:062024-04-21 07:34:07

Judging History

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

  • [2024-10-31 10:22:30]
  • hack成功,自动添加数据
  • (/hack/1089)
  • [2024-04-21 07:34:07]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3984kb
  • [2024-04-21 07:34:06]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

using T = double;
using vd = vector<T>;
using vvd = vector<vd>;
using vi = vector<int>;
const T eps = 1e-8, inf = 1 / .0;

#define MP make_pair
#define ltj(X) if (s == -1 || MP(X[j],N[j]) < MP(X[s],N[s]))s = j
#define rep(i, l, r) for(int i = l;i < r;++i)

struct LPSolver {

    int m, n;
    vi N, B;
    vvd D;

    LPSolver(const vvd &A, const vd &b, const vd &c) : m(size(b)), n(size(c)), N(n + 1), B(m), D(m + 2, vd(n + 2)) {
        rep(i, 0, m)rep (j, 0, n)D[i][j] = A[i][j];
        rep(i, 0, m) {
            B[i] = n + i;
            D[i][n] = -1;
            D[i][n + 1] = b[i];
        }
        rep(j, 0, n) {
            N[j] = j;
            D[m][j] = -c[j];
        }
        N[n] = -1;
        D[m + 1][n] = 1;
    }

    void pivot(int r, int s) {
        T *a = D[r].data(), inv = 1 / a[s];
        rep(i, 0, m + 2)
            if (i != r && abs(D[i][s]) > eps) {
                T *b = D[i].data(), inv2 = b[s] * inv;
                rep(j, 0, n + 2)b[j] -= a[j] * inv2;
                b[s] = a[s] * inv2;
            }
        rep(j, 0, n + 2)if (j != s)D[r][j] *= inv;
        rep(i, 0, m + 2)if (i != r)D[i][s] *= -inv;
        D[r][s] = inv;
        swap(B[r], N[s]);
    }

    bool simplex(int phase) {
        int x = m + phase - 1;
        for (;;) {
            int s = -1;
            rep(j, 0, n + 1) {
                if (N[j] != -phase) {
                    ltj(D[x]);
                }
            }
            if (D[x][s] >= -eps)return true;
            int r = -1;
            rep(i, 0, m) {
                if (D[i][s] <= eps)continue;
                if (r == -1 || MP(D[i][n + 1] / D[i][s], B[i]) < MP(D[r][n + 1] / D[r][s], B[r]))r = i;
            }
            if (r == -1)return false;
            pivot(r, s);

        }
    }

    T solve(vd &x) {
        int r = 0;
        rep(i, 1, m) if (D[i][n + 1] < D[r][n + 1])r = i;
        if (D[r][n + 1] < -eps) {
            pivot(r, n);
            if (!simplex(2) || D[m + 1][n + 1] < -eps)return -inf;
            rep(i, 0, m) if (B[i] == -1) {
                    int s = 0;
                    rep(j, 1, n + 1)ltj(D[i]);
                    pivot(i, s);
                }
        }
        bool ok = simplex(1);
        x = vd(n);
        rep(i, 0, m)if (B[i] < n) x[B[i]] = D[i][n + 1];
        return ok ? D[m][n + 1] : inf;
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(false);
    int n;
    cin >> n;
    vvd a(n, vd(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j)cin >> a[i][j];
        a[i][i] = 0;
    }
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            a[j][i] = a[i][j];
        }
    }
    double res = 0.0;
    for (int mask = 1; mask < (1 << n); ++mask) {
        vector<int> all;
        for (int i = 0; i < n; ++i) {
            if ((1 << i) & mask)all.push_back(i);
        }
        int w = all.size();
        vvd A;
        vd b, c, x;
        // Sum of e = 1
        A.emplace_back(vd(w, 1));
        b.emplace_back(1);
        A.emplace_back(vd(w, -1));
        b.emplace_back(-1);
        // fs
        int who = all[0];
        for (int i = 1; i < all.size(); ++i) {
            A.emplace_back();
            for (auto j: all) {
                A.back().emplace_back(a[all[i]][j] - a[who][j]);
            }
            b.push_back(0);
            A.emplace_back();
            for (auto j: all) {
                A.back().emplace_back(-a[all[i]][j] + a[who][j]);
            }
            b.push_back(0);
        }
        for (auto j: all) {
            c.push_back(a[who][j]);
        }
        T f = LPSolver(A, b, c).solve(x);
        assert(f > -eps);
        res = max(res, f / 2);
    }
    cout << fixed << setprecision(20);
    cout << res;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3984kb

input:

2
0 1
1 0

output:

0.25000000000000000000

result:

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

Test #2:

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

input:

3
0 2 1
2 0 2
1 2 0

output:

0.57142857142857150787

result:

ok found '0.5714286', expected '0.5714290', error '0.0000004'

Test #3:

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

input:

3
0 1 2
1 0 1
2 1 0

output:

0.50000000000000000000

result:

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

Test #4:

score: -100
Runtime Error

input:

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

output:


result: