結果

問題 No.1122 Plane Tickets
ユーザー hitonanode
提出日時 2021-02-11 23:40:45
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 1,000 ms
コード長 4,019 bytes
コンパイル時間 9,058 ms
コンパイル使用メモリ 315,152 KB
最終ジャッジ日時 2025-01-18 17:43:57
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 55
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

ソースコード

diff # 

#pragma once
#include <cmath>
#include <numeric>
#include <vector>

// CUT begin
// Maximize cx s.t. Ax <= b, x >= 0
// Implementation idea: https://kopricky.github.io/code/Computation_Advanced/simplex.html
// Refer to https://hitonanode.github.io/cplib-cpp/combinatorial_opt/simplex.hpp
template <typename Float = double, int DEPS = 30> struct Simplex {
    const Float EPS = Float(1.0) / (1LL << DEPS);
    int N, M;
    std::vector<int> idx;
    std::vector<std::vector<Float>> a;
    int i_ch, j_ch;

    void initialize(const std::vector<std::vector<Float>> &A, const std::vector<Float> &b, const std::vector<Float> &c) {
        N = c.size(), M = A.size();

        a.assign(M + 2, std::vector<Float>(N + 2));
        i_ch = M;
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) a[i][j] = -A[i][j];
            a[i][N] = 1, a[i][N + 1] = b[i];
            if (a[i_ch][N + 1] > a[i][N + 1]) i_ch = i;
        }
        for (int j = 0; j < N; j++) a[M][j] = c[j];
        a[M + 1][N] = -1;

        idx.resize(N + M + 1);
        std::iota(idx.begin(), idx.end(), 0);
    }

    inline Float abs_(Float x) noexcept { return x > -x ? x : -x; }
    void solve() {
        std::vector<int> jupd;
        for (j_ch = N;;) {
            if (i_ch < M) {
                std::swap(idx[j_ch], idx[i_ch + N + 1]);
                a[i_ch][j_ch] = Float(1) / a[i_ch][j_ch];
                jupd.clear();
                for (int j = 0; j < N + 2; j++) {
                    if (j != j_ch) {
                        a[i_ch][j] *= -a[i_ch][j_ch];
                        if (abs_(a[i_ch][j]) > EPS) jupd.push_back(j);
                    }
                }
                for (int i = 0; i < M + 2; i++) {
                    if (abs_(a[i][j_ch]) < EPS or i == i_ch) continue;
                    for (auto j : jupd) a[i][j] += a[i][j_ch] * a[i_ch][j];
                    a[i][j_ch] *= a[i_ch][j_ch];
                }
            }

            j_ch = -1;
            for (int j = 0; j < N + 1; j++) {
                if (j_ch < 0 or idx[j_ch] > idx[j]) {
                    if (a[M + 1][j] > EPS or (abs_(a[M + 1][j]) < EPS and a[M][j] > EPS)) j_ch = j;
                }
            }
            if (j_ch < 0) break;

            i_ch = -1;
            for (int i = 0; i < M; i++) {
                if (a[i][j_ch] < -EPS) {
                    if (i_ch < 0) {
                        i_ch = i;
                    } else if (a[i_ch][N + 1] / a[i_ch][j_ch] - a[i][N + 1] / a[i][j_ch] < -EPS) {
                        i_ch = i;
                    } else if (a[i_ch][N + 1] / a[i_ch][j_ch] - a[i][N + 1] / a[i][j_ch] < EPS and idx[i_ch] > idx[i]) {
                        i_ch = i;
                    }
                }
            }
            if (i_ch < 0) {
                is_infty = true;
                break;
            }
        }
        if (a[M + 1][N + 1] < -EPS) {
            infeasible = true;
            return;
        }
        x.assign(N, 0);
        for (int i = 0; i < M; i++) {
            if (idx[N + 1 + i] < N) x[idx[N + 1 + i]] = a[i][N + 1];
        }
        ans = a[M][N + 1];
    }
    Simplex(const std::vector<std::vector<Float>> &A, const std::vector<Float> &b, const std::vector<Float> &c) {
        is_infty = infeasible = false;
        initialize(A, b, c);
        solve();
    }
    bool is_infty;
    bool infeasible;
    std::vector<Float> x;
    Float ans;
};
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <iostream>
#include <vector>
#define PROBLEM "https://yukicoder.me/problems/no/1122"
using namespace std;

int main() {
    using Float = boost::multiprecision::cpp_dec_float_50;
    vector<Float> B(5);
    for (auto &x : B) cin >> x;
    vector<vector<Float>> A{{1, 1, 1, 0, 0}, {0, 1, 1, 1, 0}, {0, 0, 1, 1, 1}, {1, 0, 0, 1, 1}, {1, 1, 0, 0, 1}};
    vector<Float> C(5, 1);
    Simplex<Float, 30> simplex(A, B, C);
    cout << llround(simplex.ans - 0.17) << '\n'; // I haven't proved yet this always returns correct answer.
}
0