제출 #973568

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
973568		socpite	통행료 (APIO13_toll)	C++14	0 / 100	1 ms	6748 KiB

toll

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5+5;
const int INF = 1e9;

int n, m, k, cnt, rt;
int up1[maxn], up2[maxn];
int p_real[maxn], p[maxn], id[maxn], dp[maxn], dep[maxn], par[maxn], mark[maxn], mn[maxn];
bool in_tree[maxn];

long long ans = 0;

int Find(int x, int* up){
    return up[x] < 0 ? x : up[x] = Find(up[x], up);
}

bool Union(int a, int b, int* up){
    a = Find(a, up);
    b = Find(b, up);
    if(a == b)return false;
    up[a] += up[b];
    up[b] = a; 
    return true;
}

vector<pair<int, int>> g[maxn];

vector<pair<int, pair<int, int>>> E1, E2, important;
vector<pair<int, int>> fake;

void pre_dfs(int x){
    dp[x] = p_real[x];
    mn[x] = INF;
    for(auto v: g[x]){
        if(v.first == par[x])continue;
        dep[v.first] = dep[x] + 1;
        par[v.first] = x;
        pre_dfs(v.first);
        dp[x] += dp[v.first];
        mark[v.first] = v.second;
    }
}

void solve(int mask){
    for(int i = 1; i <= cnt; i++){
        up1[i] = -1;
        g[i].clear();
    }
    for(int i = 0; i < k; i++){
        if(!(mask&(1<<i)))continue;
        if(!Union(fake[i].first, fake[i].second, up1))return;
        g[fake[i].first].push_back({fake[i].second, 1});
        g[fake[i].second].push_back({fake[i].first, 1});
    }
    for(int i = 0; i < important.size(); i++){
        auto v = important[i];
        in_tree[i] = Union(v.second.first, v.second.second, up1);
        if(in_tree[i]){
            g[v.second.first].push_back({v.second.second, 0});
            g[v.second.second].push_back({v.second.first, 0});
        }
    }
    pre_dfs(rt);
    for(int i = 0; i < important.size(); i++){
        if(in_tree[i])continue;
        int w = important[i].first, a = important[i].second.first, b = important[i].second.second;
        // cout << w << " " << a << " " << b << endl;
        while(a != b){
            if(dep[a] < dep[b])swap(a, b);
            mn[a] = w;
            a = par[a];
        }
    }
    long long sum = 0;
    for(int i = 1; i <= cnt; i++){
        if(mark[i])sum += mn[i]*dp[i];
    }
    ans = max(ans, sum);

}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> k;
    E1.resize(m);
    for(auto &v: E1)cin >> v.second.first >> v.second.second >> v.first;
    sort(E1.begin(), E1.end());
    for(int i = 1; i <= n; i++)up1[i] = -1;
    for(auto v: E1){
        if(Union(v.second.first, v.second.second, up1))E2.push_back(v);
    }    
    fake.resize(k);
    for(auto &v: fake)cin >> v.first >> v.second;
    for(int i = 1 ; i <= n; i++){
        up1[i] = -1;
        cin >> up2[i];
        up2[i] *= -1;
    }
    for(auto v: fake)Union(v.first, v.second, up1);
    for(auto v: E2){
        if(Union(v.second.first, v.second.second, up1))Union(v.second.first, v.second.second, up2);
        else important.push_back(v);
    }
    for(int i = 1; i <= n; i++){
        if(up2[i] < 0){
            cnt++;
            id[i] = cnt;
            p_real[cnt] = -up2[i];
        }
    }
    rt = id[Find(1, up2)];
    for(auto &v: fake){
        v.first = id[Find(v.first, up2)];
        v.second = id[Find(v.second, up2)];
        // cout << v.first << " " << v.second << endl;
    }
    for(auto &v: important){
        v.second.first = id[Find(v.second.first, up2)];
        v.second.second = id[Find(v.second.second, up2)];
        // cout << v.second.first << " " << v.second.second << endl;
    }
    for(int i = 1; i < (1<<k); i++)solve(i);
    cout << ans;
}

컴파일 시 표준 에러 (stderr) 메시지

toll.cpp: In function 'void solve(int)':
toll.cpp:56:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for(int i = 0; i < important.size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~~
toll.cpp:65:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for(int i = 0; i < important.size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~~

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