可降难度,数据巨水,放心暴搜。
查看原帖
可降难度,数据巨水,放心暴搜。
134593
反手一只MJJ楼主2024/10/22 22:34

rt。随便写的垃圾代码也能过,不是凡尔赛,真的是题目数据太水导致大家都被动凡尔赛。不够蓝题难度,可降。

#include <cstdio>
#include <iostream>
#include <cctype>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <set>
#include <map>
#include <string>
#include <bitset>
#include <stack>
#include <random>
#include <functional>
using namespace std;
typedef unsigned long long ull;
typedef long long int ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
constexpr ll MAXN = 3e5 + 10;
constexpr ll MOD = 1e9 + 7;
constexpr ll INF = 1ll << 62;
#define mkp make_pair
#define stop 1 == 1;
#define lt root << 1
#define rt root << 1 | 1

template<typename T> void read_single(T& x){
    x = 0;
    char g = getchar();
    bool f = true;
    while(!isdigit(g)){if(g == '-')f = !f;g = getchar();}
    while(isdigit(g)){x = (x << 1) + (x << 3) + (g ^ 48);g = getchar();}
    x = f ? x : -x;
}
void read(){}
template<typename T, typename... Args>
void read(T& x, Args&... args) {
    read_single(x);
    read(args...);
}
template<typename T> void write(T x){
    if(x < 0){putchar('-');x = -x;}
    if(x > 9)write(x / 10);
    putchar(x % 10 ^ 48);
}

struct Edge{
    ll idx, w;
    vector<ll> adj[2];
    unordered_map<ll, int> toSide;
};

void dfs(vector<Edge>& e,
         ll& sum, ll Idx, int Trn,
         vector<bool>& vis, ll& ans,
         ll fa, ll u){
    auto&c = e[u];
    
    sum += c.w;
    vis[u] = true;
    int trn = c.toSide[fa] ^ 1;
    
    auto finish = c.adj[trn].end();
    auto iter = lower_bound(c.adj[trn].begin(), finish, Idx);
    for(;iter != finish; iter++){
        auto v = *iter;
        if(v == Idx && e[v].toSide[u] == Trn){
            ans = min(ans, sum);
        }
        if(vis[v])continue;
        dfs(e, sum, Idx, Trn, vis, ans, u, v);
    }
    
    sum -= c.w;
    vis[u] = false;
};

void solve(){
    ll N; read(N);
    vector<ll> changeIdx(N + 1);
    for(ll i = 0; i <= N; i++)changeIdx[i] = i;
    random_device rd;
    mt19937 G(rd());
    shuffle(changeIdx.begin() + 1, changeIdx.end(), G);
    
    vector<Edge> e(N + 1);
    ll n[2];
    for(int k = 1; k <= N; k++){
        auto& c = e[k];
        read(c.idx, c.w, n[0], n[1]);
        c.idx = changeIdx[c.idx];
        
        for(int i = 0; i < 2; i++){
            while(n[i]--){
                ll jdx; read(jdx);
                jdx = changeIdx[jdx];
                c.adj[i].emplace_back(jdx);
                c.toSide[jdx] = i;
            }
            sort(c.adj[i].begin(), c.adj[i].end());
        }
    }
    sort(e.begin() + 1, e.end(), [&](const Edge& a, const Edge& b){
        return a.idx < b.idx;
    });
    
    ll ans = INF;
    
    for(int k = 1; k <= N; k++){
        auto& c = e[k];
        ll u = c.idx;
        if(c.adj[0].back() < c.idx || c.adj[1].back() < c.idx)continue; // 剪枝
        
        ll sum = c.w;
        vector<bool> vis(101, false);
        vis[u] = true;
        auto finish = c.adj[0].end();
        auto iter = lower_bound(c.adj[0].begin(), finish, c.idx);
        
        for(;iter != finish; iter++){
            auto v = *iter;
            dfs(e, sum, u, 1, vis, ans, u, v);
        }
    }

    write(ans);
    cout << flush;
    return;
}

int main(){
    cin.tie(0);cout.tie(0);
    ios::sync_with_stdio(false);

    ll T = 1;
//    read(T);
    while(T--){
        solve();
    }
    return 0;
}
/*
 10
 1 16 2 2
 2 7
 10 6
 2 3 2 2
 1 7
 8 3
 3 3 2 1
 8 2
 4
 4 8 1 3
 3
 9 10 5
 5 8 3 1
 9 10 4
 6
 6 6 1 2
 5
 1 10
 7 5 2 2
 1 2
 8 9
 8 4 2 2
 2 3
 7 9
 9 5 2 3
 7 8
 4 5 10
 10 10 2 3
 1 6
 4 9 5
 
 */

2024/10/22 22:34
加载中...