E. Cheap Dinner(Educational Codeforces Round 104 (Rated for Div. 2))题解

本文主要是介绍E. Cheap Dinner(Educational Codeforces Round 104 (Rated for Div. 2))题解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目链接：E. Cheap Dinner
题意：略
思路：一开始先写了一个\(n^2\)的\(dp\)，然后发现是T，证明方法没什么问题，然后发现他虽然能连接的边数目是\(n^2\)不过不能连接的边最多也就\(1e5\)这个级别，就算一个一个遍历也可以接受，不如从第一号菜开始，sort根据第一号菜大小排序，然后对于第二号菜来说，去已排序的第一号菜中找到自己能够搭配的最小的一号菜品，因为一号菜与二号菜的不能连接的个数只有150000条，所以最坏情况下这150000个第二道菜最多需要\(150000 + 150000\)次的寻找，这有点类似于\(Mex\)操作，然后将更新了第二道菜的贡献的数组重新排序并计算饮料对第二道菜的影响。因为边还需要用map存一下，所以复杂度\(\Theta(nlognlogn)\)，可以接受。
\(Code:\)

#include<set>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<map>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define lowbit(x) (x&(-x))
#define ch() getchar()
#define x first
#define y second
#define pc(x) putchar(x)
using namespace std;

template<typename T>void read(T&x){
static char c;static int f;
for(c=ch(),f=1;c<'0'||c>'9';c=ch())if(c=='-')f=-f;
for(x=0;c>='0'&&c<='9';c=ch())x=x*10+(c&15);x*=f;
}
template<typename T>void write(T x){
static char q[65];int cnt=0;
if(x<0)pc('-'),x=-x;
q[++cnt]=x%10,x/=10;
while(x)
    q[++cnt]=x%10,x/=10;
while(cnt)pc(q[cnt--]+'0');
}

const int N = 2e5+10,inf = 0x3f3f3f3f;
int n[6],m[6],a[5][N];
vector<int>G[5][N];
struct node {
    int id,data;
    bool operator<(const node &a)const{
        return a.data>data;
    }
}f[N],c[N];
map<pair<int,int>,bool>S[5];
bool st[N];
void work(){
    rep(j,1,n[1])f[j] = {j,a[1][j]};
    sort(f+1,f+1+n[1]);
    int tot = n[1];
    rep(i,2,4){
        rep(j,1,n[i]){
            int sum = -1;
            st[j] = false;
            rep(k,1,tot){
                if(!S[i][{j,f[k].id}]){sum = f[k].data; break; }//continue;
            }
            if(sum == -1)st[j] = true;
            c[j] = {j,a[i][j] + sum};
        }
        tot = 0;
        rep(j,1,n[i]){if(st[j] == false) f[++tot] = c[j];}
        if(!tot){
            puts("-1");return ;
        }
        sort(f+1,f+1+tot);
    }
    write(f[1].data);pc('\n');
}
void solve(){
    rep(i,1,4)read(n[i]);
    rep(i,1,4){
        rep(j,1,n[i]){
            read(a[i][j]);
        }
    }
    rep(i,1,3){
        read(m[i]);
        rep(j,1,m[i]){
            int u,v;
            read(u);read(v);
            S[i+1][{v,u}] = true;
        }
    }
    work();
}
signed main(){solve();return 0;}

这篇关于E. Cheap Dinner(Educational Codeforces Round 104 (Rated for Div. 2))题解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！