Cheap Dinner

Created by LXC on Wed Feb 28 15:05:43 2024

https://codeforces.com/problemset/problem/1487/E

ranting: 2000

tag: brute force, data structures, graphs, greedy, implementation, sortings, two pointers

problem

题目描述

有 $4$ 种菜类——开胃菜，主菜，饮品和甜点。一顿晚饭由 $4$ 种菜类各一道组成。

对于第 $i$ 种菜类，共有 $n_i$ 种供选择。开胃菜、主菜、饮品和甜点价格分别为 $a_i$、$b_i$、$c_i$、$d_i$。

有些菜品不能搭配。对于开胃菜和主菜来说，有 $m_1$ 对不能搭配。对于主菜和饮品、饮品和甜点分别有 $m_2$，$m_3$ 对。

试问总价格最小的晚饭需要多少钱？

输入

第一行有 $n_1$、$n_2$、$n_3$、$n_4$；

接下来四行分别为 $a_i$，$b_i$，$c_i$，$d_i$；

接下来一行为 $m_1$，接下来 $m_1$ 行中，每一行有 $x_i$，$y_i$，表示第 $x_i$ 道开胃菜和第 $y_i$ 道主菜不能搭配。

主菜和饮品，饮品和甜点的搭配需求也以相同的方式输入。

输出

如果不存在，输出 -1；

否则，输出最小花费。

数据规模

$1\le n_i\le 150000$，$0\le m_i\le 200000$，$1\le a_i,b_i,c_i,d_i\le 10^8$。

保证 $1\le x_i\le n_t$，$1\le y_i\le n_{t+1}$，且对于相同的 $t$，$(x_i,y_i)$ 互不相同。

solution

设$f_{i,j}$为已经选了i道菜，且第i道菜选择第j种菜的最大值。

初始化$f_{1, i} = a_{i}$

答案就是$\min f_{4, i}$

转移$f_{i,j} = a_{i,j} + \min \limits_{<k,j> \ is \ available} f_{i-1,k}$

例如我们可以记录每种第二道菜$i$有多少条指向第一道菜的边$e_i$，由于$\sum e_i = m_1$，我们可以先用平衡树存储所有的第一道菜种类，然后对于第二道菜的种类i，直接在平衡树种删除$e_i$道菜，花费时间$O(e_ilogn_1)$，然后查询平衡树中最小值作为$f_{2,i}$的转移来源。最后将删除的$e_i$道菜重新加入平衡树，求出所有$f_{2,?}$的复杂度为$O(m_1logn_1)$

总复杂度$O(\sum m_ilogn_i)$

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}
template<class t> ostream& operator<<(ostream& os,const multiset<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}


void sol() {
    int n[4];
    for (int i=0; i<4; i++) cin >> n[i];
    vector<vector<ll>> a(4), dp(4);
    for (int i=0; i<4; i++) {
        dp[i].resize(n[i], -1);
        for (int j=0; j<n[i]; j++) {
            int x;
            cin >> x;
            a[i].push_back(x);
        }
    }
    vector<vector<vector<int>>> g(3);
    for (int i=0; i<3; i++) {
        int t;
        cin >> t;
        g[i].resize(n[i+1]);
        while (t--) {
            int x, y;
            cin >> x >> y;
            x--; y--;
            g[i][y].push_back(x);
        }
    }
    dp[0] = a[0];
    for (int i=1; i<=3; i++) {
        multiset<ll> st(dp[i-1].begin(), dp[i-1].end());
        for (int j=0; j<n[i]; j++) {
            for (int k:g[i-1][j]) {
                st.erase(st.find(dp[i-1][k]));
            }
            if (st.size())
                dp[i][j] = *st.begin()+a[i][j];
            else 
                dp[i][j] = MOD;
            for (int k:g[i-1][j]) {
                st.insert(dp[i-1][k]);
            }
        }
        // cout << dp[i] << endl;
    }
    // cout << dp << endl;
    int ans = *min_element(dp[3].begin(), dp[3].end());
    cout << (ans>=MOD?-1:ans) << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}