제출 #872869

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
872869		gggkik	통행료 (APIO13_toll)	C++14	16 / 100	9 ms	4440 KiB

toll

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct dsu{
    vector<int> par;
    void init(int x){
        par.resize(x+1);
        iota(par.begin(),par.end(),0);
    }
    int find(int x){
        return par[x]-x?par[x]=find(par[x]):x;
    }
    void u(int a,int b){
        a = find(a), b = find(b);
        if(a!=b) par[a] = b;
    }
};
vector<vector<int>> build_mst(int n, vector<vector<int>> edges){
    dsu uf; uf.init(n);
    sort(edges.begin(),edges.end(),[&](vector<int> &i, vector<int> &j){
        return i[2]<j[2];
    });
    vector<vector<int>> ret;
    for(auto &i : edges){
        int a = uf.find(i[0]), b = uf.find(i[1]);
        if(a!=b) {
            uf.u(a,b);
            ret.push_back(i);
        }
    }
    return ret;
}
const int MXN = 1e5+5;
using pii = pair<int,int>;
using ll = long long;
vector<pii> E[MXN];
void build(int n,vector<vector<int>> &v){
    for(int i = 1;i<=n;i++) E[i].clear();
    for(auto &j : v){
        E[j[0]].push_back({j[1],j[2]});
        E[j[1]].push_back({j[0],j[2]});
    }
}
ll sz[MXN], A[MXN];
void dfs(int x,int p,vector<ll> &v){
    sz[x] = A[x];
    for(auto i : E[x]) if(i.first!=p){
        dfs(i.first,x,v);
        if(!i.second) v.push_back(sz[i.first]);
        sz[x] += sz[i.first];
    }
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, m, k; cin >> n >> m >> k;
    vector<vector<int>> edges;
    for(int i = 0;i<m;i++){
        int a,b,c; cin >> a >> b >> c;
        edges.push_back({a,b,c});
    }
    edges = build_mst(n, edges);
    vector<vector<int>> myedge;
    for(int i = 0;i<k;i++){
        int a,b; cin >> a >> b;
        myedge.push_back({a,b,0});
    }
    ll sum = 0;
    for(int i = 1;i<=n;i++) {cin >> A[i]; sum += A[i];}
    ll ans = 0;
    for(int i = 0;i<1<<k;i++){
        vector<vector<int>> EDGE = edges;
        for(int j = 0;j<k;j++) if(i>>j&1)
            EDGE.push_back(myedge[j]);
        set<int> S;
        for(auto &j : EDGE) S.insert(j[2]);
        EDGE = build_mst(n,EDGE);
        for(auto &j : EDGE) S.erase(j[2]);
        vector<ll> v;
        build(n,EDGE);
        dfs(1,0,v);
        if(sz[1]!=sum) continue;
        ll cost = 0;
        //cout << i << " :: \n";
        sort(v.begin(),v.end());
        //for(int j = 1;j<=n;j++) cout << sz[j] << ' '; cout << endl;
        for(;v.size();){
            ll x = v.back(); v.pop_back();
            //cout << x << ' ' << *prev(S.end()) << endl;
            cost += x**prev(S.end()); S.erase(prev(S.end()));
        }
        //cout << ' ' << cost << endl;
        ans = max(cost,ans);
    }
    cout << ans;
}

• Subtask 1: 16 / 16
• Subtask 2: 0 / 18
• Subtask 3: 0 / 22
• Subtask 4: 0 / 22
• Subtask 5: 0 / 22