제출 #1279752

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1279752		longdeptrai	Cities (BOI16_cities)	C++20	22 / 100	101 ms	3368 KiB

cities

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (ll)9e18;

struct Edge {
    int u, v;
    ll w;
};

struct DSU {
    vector<int> p, r;
    DSU(int n=0){ init(n); }
    void init(int n){ p.resize(n); r.assign(n,0); iota(p.begin(), p.end(), 0); }
    int find(int x){ return p[x]==x?x:p[x]=find(p[x]); }
    bool unite(int a,int b){
        a = find(a); b = find(b);
        if(a==b) return false;
        if(r[a]<r[b]) swap(a,b);
        p[b]=a;
        if(r[a]==r[b]) r[a]++;
        return true;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n,k,m;
    if(!(cin>>n>>k>>m)) return 0;
    vector<int> terminals(k);
    for(int i=0;i<k;i++){
        cin>>terminals[i];
        terminals[i]--; // zero-based
    }
    vector<Edge> edges;
    edges.reserve(m);
    for(int i=0;i<m;i++){
        int u,v; ll w;
        cin>>u>>v>>w;
        u--; v--;
        edges.push_back({u,v,w});
    }

    // nếu n quá lớn, phương pháp này sẽ chậm; ta cảnh báo nhưng vẫn chạy.
    if(n > 23){
        // với n>23, 2^n quá lớn để liệt kê tập đỉnh; bạn nên dùng DP-Steiner.
        // Nhưng vẫn cố chạy nếu người dùng muốn (có thể rất chậm).
    }

    // bitmask terminals requirement
    int needMask = 0;
    for(int t: terminals) needMask |= (1<<t);

    // Nhưng needMask above incorrectly uses full n-bit indexing.
    // Vì n có thể > 31 (bit shift overflow). To avoid this, we should map vertices
    // to bits only when n <= 30. We assume n <= 20 per subtask. If n > 30, stop.
    if(n > 30){
        cerr << "n too large for subset-enumeration approach (n should be <=~30)\n";
        return 0;
    }

    // Build bitmask of terminals for n bits (safe since we guard n<=30)
    int termMask = 0;
    for(int t: terminals) termMask |= (1<<t);

    ll ans = INF;
    int FULL = 1<<n;
    // Enumerate all vertex subsets mask: mask indicates which vertices are included
    for(int mask = 0; mask < FULL; ++mask){
        // must include all terminals
        if( (mask & termMask) != termMask ) continue;

        int cntV = __builtin_popcount(mask);
        if(cntV <= 1) continue; // can't connect >=2 terminals unless cntV>1

        // collect edges internal to mask
        vector<pair<ll, pair<int,int>>> E;
        E.reserve(m);
        for(auto &e: edges){
            if( (mask & (1<<e.u)) && (mask & (1<<e.v)) ){
                E.push_back({e.w, {e.u, e.v}});
            }
        }
        if((int)E.size() < cntV-1) continue; // not enough edges to connect

        sort(E.begin(), E.end(), [](auto &a, auto &b){ return a.first < b.first; });

        DSU dsu(n);
        ll total = 0;
        int used = 0;
        for(auto &ee: E){
            int u = ee.second.first;
            int v = ee.second.second;
            ll w = ee.first;
            if(dsu.unite(u,v)){
                total += w;
                used++;
                if(used == cntV - 1) break;
            }
        }
        if(used == cntV - 1){
            ans = min(ans, total);
        }
    }

    if(ans == INF) {
        // theo đề sẽ luôn có đường đi giữa mọi đôi đỉnh, nên ko hy vọng vô nghiệm
        cout << "-1\n";
    } else {
        cout << ans << "\n";
    }

    return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 26