답안 #220090

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
220090 2020-04-06T23:42:37 Z osaaateiasavtnl 통행료 (APIO13_toll) C++14
100 / 100
2041 ms 22312 KB
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
const int N = 3e5 + 7, K = 23, INF = 1e9 + 7;
struct Edge { int u, v, c; bool in; };  
bool comp(Edge a, Edge b) { return a.c < b.c; }
int root(int u, int *par) {
    if (par[u] == u) return u;
    else return par[u] = root(par[u], par);
}   
int par[N], par1[N], w[N], num[N], ww[K];
int n, m, k;
bool in[N];
int small_par[K];
vector <pair <int, bool> > g[K];
int tree_par[K];
int h[K], cnt[K], up[K];
void dfs(int u, int p) {
    tree_par[u] = p;
    cnt[u] = ww[u];
    for (auto e : g[u]) {
        int v = e.f;
        if (v != p) {
            //cout << "go " << u << ' ' << e.f << ' ' << e.s << endl;
            h[v] = h[u] + 1;
            if (e.s)
                up[v] = INF;
            else
                up[v] = 0;
            dfs(v, u);
            cnt[u] += cnt[v];
        }   
    }
}   
void getup(int &u, int c) {
    up[u] = min(up[u], c);
    u = tree_par[u];
}   
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    cin >> n >> m >> k;
    vector <Edge> ev;
    for (int i = 0; i < m; ++i) {
        int u, v, c; cin >> u >> v >> c;
        ev.app({u, v, c, 0});
    }   
    sort(all(ev), comp);
    for (int i = 1; i <= n; ++i) par[i] = i;
    for (auto &e : ev) {
        if (root(e.u, par) != root(e.v, par)) {
            e.in = 1;
            par[root(e.u, par)] = root(e.v, par);
        }   
    }   
    for (int i = 1; i <= n; ++i) par[i] = par1[i] = i;
    vector <ii> add;
    for (int i = 0; i < k; ++i) {
        int u, v; cin >> u >> v;
        add.app(mp(u, v));
        if (root(u, par) != root(v, par))
            par[root(u, par)] = root(v, par);
    }   
    vector <Edge> small;
    for (auto &e : ev) {
        if (root(e.u, par) != root(e.v, par)) {
            par[root(e.u, par)] = root(e.v, par);
            par1[root(e.u, par1)] = root(e.v, par1);
        }
        else if (e.in) 
            small.app(e);
    }   
    int ptr = 0;
    for (int i = 1; i <= n; ++i)
        if (par1[i] == i)
            num[i] = ++ptr;
    for (int i = 1; i <= n; ++i) {
        cin >> w[i];
        ww[num[root(i, par1)]] += w[i];
    }
    int troot = num[root(1, par1)];
    sort(all(small), comp);
    for (auto &e : small) {
        e.u = num[root(e.u, par1)];
        e.v = num[root(e.v, par1)];
    }   
    for (auto &e : add) {
        e.f = num[root(e.f, par1)];
        e.s = num[root(e.s, par1)];
    }   
    int ans = 0;
    for (int mask = 0; mask < (1 << k); ++mask) {
        for (int i = 0; i < K; ++i) {
            small_par[i] = i;
            g[i].clear();
        }
        bool cyc = 0;
        for (int i = 0; i < k; ++i)
            if ((mask >> i) & 1) {
                int u = add[i].f, v = add[i].s;
                if (root(u, small_par) == root(v, small_par)) {
                    cyc = 1;
                    break;
                }   
                small_par[root(u, small_par)] = root(v, small_par);
                g[u].app({v, 1}); g[v].app({u, 1});
                //cout << "edge " << u << ' ' << v << ' ' << 1 << endl;
            }   
        if (cyc)
            continue;
        vector <Edge> rel;                                        
        for (auto e : small) {
            if (root(e.u, small_par) == root(e.v, small_par)) 
                rel.app(e);
            else {
                small_par[root(e.u, small_par)] = root(e.v, small_par);
                g[e.u].app({e.v, 0}); g[e.v].app({e.u, 0});               
                //cout << "edge " << e.u << ' ' << e.v << ' ' << 0 << endl;
            }                   
        }   
        dfs(troot, troot);
        /*
        cout << "up : ";
        for (int i = 1; i <= ptr; ++i)
            cout << up[i] << ' ';
        cout << endl;
        */
        for (auto e : rel) {
            int u = e.u, v = e.v;
            while (h[u] > h[v]) 
                getup(u, e.c);
            while (h[v] > h[u]) 
                getup(v, e.c);
            while (u != v) {
                getup(u, e.c);
                getup(v, e.c);
            }
        }   
        //cout << "mask " << mask << endl;
        int nn = 0;
        for (int i = 1; i <= ptr; ++i)
            if (i != troot) {
                //cout << i << ' ' << cnt[i] << ' ' << up[i] << endl;
                nn += cnt[i] * up[i];
            }
        ans = max(ans, nn);
    }   
    cout << ans << endl;
}   
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 8 ms 768 KB Output is correct
6 Correct 8 ms 768 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 8 ms 768 KB Output is correct
6 Correct 8 ms 768 KB Output is correct
7 Correct 268 ms 22200 KB Output is correct
8 Correct 300 ms 22312 KB Output is correct
9 Correct 272 ms 22100 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 8 ms 768 KB Output is correct
6 Correct 8 ms 768 KB Output is correct
7 Correct 268 ms 22200 KB Output is correct
8 Correct 300 ms 22312 KB Output is correct
9 Correct 272 ms 22100 KB Output is correct
10 Correct 1777 ms 22100 KB Output is correct
11 Correct 2041 ms 22100 KB Output is correct
12 Correct 2040 ms 22268 KB Output is correct