結果

問題 No.119 旅行のツアーの問題
ユーザー shobonvip
提出日時 2024-04-02 08:25:58
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 18 ms / 5,000 ms
コード長 3,320 bytes
コンパイル時間 2,963 ms
コンパイル使用メモリ 219,980 KB
最終ジャッジ日時 2025-02-20 19:33:42
ジャッジサーバーID
（参考情報） 		judge1 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<bits/stdc++.h>
using namespace std;
#include<atcoder/maxflow>
template <typename T>
struct MoyasuUmeru {
    int n, s, t;
    T geta;
    vector<vector<T>> cost;
    atcoder::mf_graph<T> graph;
    MoyasuUmeru(int n):
        n(n),
        s(n),
        t(n+1),
        geta(0),
        cost(2),
        graph(0) {
            graph = atcoder::mf_graph<T>(n+2);
            cost[0].resize(n);
            cost[1].resize(n);
        }
    void add_cost(int i, int state, T val){
        cost[state][i] += val;
    }
    void add_constraint(int x, int y, const vector<vector<T>> &cs){
        T a = cs[0][0];
        T b = cs[0][1];
        T c = cs[1][0];
        T d = cs[1][1];
        geta += a;
        add_cost(x, 1, c - a);
        add_cost(y, 1, d - c);
        assert(b + c - a - d >= 0);
        graph.add_edge(x, y, b + c - a - d);
    }
    pair<T, vector<int>> solve(){
        for (int i=0; i<n; i++){
            if (cost[0][i] <= cost[1][i]){
                graph.add_edge(s, i, cost[1][i] - cost[0][i]);
                geta += cost[0][i];
            }else{
                graph.add_edge(i, t, cost[0][i] - cost[1][i]);
                geta += cost[1][i];
            }
        }
        T ret1 = geta + graph.flow(s, t);
        vector<bool> result = graph.min_cut(s);
        vector<int> ret2(n);
        for (int i=0; i<n; i++){
            if (result[i]){
                ret2[i] = 1;                
            }
        }
        return pair(ret1, ret2);
    };
};
template<typename T>
struct KvaluedMoyasuUmeru {
    int n;
    int alls;
    vector<int> k;
    MoyasuUmeru<T> mf;
    vector<int> offset;
    T geta;
    KvaluedMoyasuUmeru(const vector<int> &kk, T INF):
        k(kk), n((int)kk.size()), alls(0), geta(0), mf(0), offset(n) {
            for (int i=0; i<n; i++){
                assert(k[i] >= 1);
            }
            for (int i=0; i<n-1; i++){
                offset[i+1] = offset[i] + k[i] - 1;
            }
            alls = offset[n-1] + k[n-1] - 1;
            mf = MoyasuUmeru<T>(alls);
            for (int i=0; i<n; i++){
                for (int j=0; j<k[i]-2; j++){
                    mf.graph.add_edge(offset[i] + j + 1, offset[i] + j, INF);
                }
            }
        }
    
    void add_1v(int i, const vector<T> &val){
        assert((int)val.size() == k[i]);
        geta += val[k[i]-1];
        for (int j=0; j<k[i]-1; j++){
            mf.add_cost(offset[i] + j, 1, val[j] - val[j+1]);
        }
    }
    void add_2v(int x, int y, const vector<vector<T>> &val){
        assert((int)val.size() == k[x]);
        assert((int)val[0].size() == k[y]);
        vector<T> add_to_x(k[x]);
        vector<T> add_to_y(k[y]);
        for (int i=0; i<k[x]; i++){
            add_to_x[i] = val[i][0];
        }
        for (int i=0; i<k[y]; i++){
            add_to_y[i] = val[0][i];
        }
        add_1v(x, add_to_x);
        add_1v(y, add_to_y);
        geta -= val[0][0];
        for (int i=0; i<k[x]-1; i++){
            for (int j=0; j<k[y]-1; j++){
                mf.add_constraint(
                    offset[x]+i,
                    offset[y]+j,
                    {
                        {val[i+1][j+1] - val[i][j+1] - val[i+1][j] + val[i][j], 0},
                        {0, 0}
                    }
                );
            }
        }
    }
    pair<T, vector<int>> solve() {
        auto [old1, old2] = mf.solve();
        T ret1 = old1 + geta;
        vector<int> ret2(n);
        for (int i=0; i<n; i++){
            ret2[i] = k[i] - 1;
            for (int j=0; j<k[i]-1; j++){
                if (old2[offset[i]+j] == 1){
                    ret2[i] = j;
                    break;
                }
            }
        }
        return pair(ret1, ret2);
    }
};
typedef long long ll;
int main(){
    int n; cin >> n;
    KvaluedMoyasuUmeru<ll> mf(vector<int>(n, 3), (ll)1e9);
    vector<ll> b(n), c(n);
    for (int i=0; i<n; i++){
        cin >> b[i] >> c[i];
        mf.add_1v(i, {-c[i], 0, -b[i]});
    }
    int m; cin >> m;
    for (int i=0; i<m; i++){
        int d, e; cin >> d >> e;
        mf.add_2v(d, e,
            {
                {0, 0, 0},
                {0, 0, 0},
                {(ll)1e9, 0, 0}
            }
        );  
    }
    auto [x1, x2] = mf.solve();
    cout << - x1 << '\n';
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0