test/aoj0415.test.cpp

• View this file on GitHub
• Last update: 2021-06-21 15:24:20+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0415

Depends on

• graph/twoedgeconnectedcomponents.cpp

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0415"
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using uint = unsigned;
using ull = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

#include "../graph/twoedgeconnectedcomponents.cpp"

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> V(n);
    for (auto &&i : V) scanf("%d", &i);
    TwoEdgeConnectedComponents G_(n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        scanf("%d %d", &u, &v);
        u--; v--;
        G_.add_edge(u, v);
    }
    int k = G_.build();
    vector<vector<int>> G(k);
    vector<ll> v(k);
    for (int i = 0; i < k; ++i) {
        for (auto &&j : G_.out[i]) {
            v[i] += V[j];
        }
    }
    for (int i = 0; i < n; ++i) {
        for (auto &&j : G_.G[i]) {
            if(G_.is_bridge(i, j)){
                G[G_.bridge[i]].emplace_back(G_.bridge[j]);
            }
        }
    }
    ll ans = 0;
    auto dfs = [&](int x, int par, auto &&f) -> void {
        ll val1 = 0, val2 = 0;
        for (auto &&i : G[x]) {
            if(i == par) continue;
            f(i, x, f);
            if(val1 <= v[i]){
                val2 = val1; val1 = v[i];
            }else if(val2 <= v[i]){
                val2 = v[i];
            }
        }
        ans = max(ans, val1+val2+v[x]);
        v[x] += val1;
    };
    dfs(0, -1, dfs);
    cout << ans << "\n";
    return 0;
}

#line 1 "test/aoj0415.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0415"
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using uint = unsigned;
using ull = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

#line 1 "graph/twoedgeconnectedcomponents.cpp"
class TwoEdgeConnectedComponents {
    void dfs(int i, int &pos){
        ord[i] = low[i] = pos++;
        int mul = 0;
        for (auto &&j : G[i]) {
            if(j == par[i] && !mul){
                mul = 1;
                continue;
            }
            if(~ord[j]){
                low[i] = min(low[i], ord[j]);
                continue;
            }
            par[j] = i;
            dfs(j, pos);
            size[i] += size[j];
            low[i] = min(low[i], low[j]);
        }
    }

    void dfs2(int i){
        out[bridge[i]].emplace_back(i);
        for (auto &&j : G[i]) {
            if(~bridge[j] || is_bridge(i, j)) continue;
            bridge[j] = bridge[i];
            dfs2(j);
        }
    }
public:
    vector<int> ord, low, par, bridge, size;
    vector<vector<int>> G, out;
    explicit TwoEdgeConnectedComponents(int n): ord(n, -1), low(n), par(n, -1), bridge(n, -1), size(n, 1), G(n){}

    inline bool is_bridge(int i, int j){
        if(ord[i] > ord[j]) swap(i, j);
        return ord[i] < low[j];
    }

    void add_edge(int u, int v){
        if(u != v){
            G[u].emplace_back(v);
            G[v].emplace_back(u);
        }
    }

    int build(){
        int n = G.size(), pos = 0;
        for (int i = 0; i < n; ++i) {
            if(ord[i] < 0) dfs(i, pos);
        }
        int k = 0;
        for (int i = 0; i < n; ++i) {
            if(!~bridge[i]){
                bridge[i] = k++;
                out.emplace_back();
                dfs2(i);
            }
        }
        return k;
    }
};
#line 21 "test/aoj0415.test.cpp"

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> V(n);
    for (auto &&i : V) scanf("%d", &i);
    TwoEdgeConnectedComponents G_(n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        scanf("%d %d", &u, &v);
        u--; v--;
        G_.add_edge(u, v);
    }
    int k = G_.build();
    vector<vector<int>> G(k);
    vector<ll> v(k);
    for (int i = 0; i < k; ++i) {
        for (auto &&j : G_.out[i]) {
            v[i] += V[j];
        }
    }
    for (int i = 0; i < n; ++i) {
        for (auto &&j : G_.G[i]) {
            if(G_.is_bridge(i, j)){
                G[G_.bridge[i]].emplace_back(G_.bridge[j]);
            }
        }
    }
    ll ans = 0;
    auto dfs = [&](int x, int par, auto &&f) -> void {
        ll val1 = 0, val2 = 0;
        for (auto &&i : G[x]) {
            if(i == par) continue;
            f(i, x, f);
            if(val1 <= v[i]){
                val2 = val1; val1 = v[i];
            }else if(val2 <= v[i]){
                val2 = v[i];
            }
        }
        ans = max(ans, val1+val2+v[x]);
        v[x] += val1;
    };
    dfs(0, -1, dfs);
    cout << ans << "\n";
    return 0;
}

Back to top page