제출 #940334

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
940334		danikoynov	통행료 (APIO13_toll)	C++14	56 / 100	2554 ms	17600 KiB

toll

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 1e5 + 10, maxm = 3e5 + 10, maxk = 21;
const ll inf = 1e18;

struct edge
{
    int v, u;
    ll w;

    edge(int _v = 0, int _u = 0, ll _w = 0)
    {
        v = _v;
        u = _u;
        w = _w;
    }

    bool operator < (const edge &e) const
    {
        return w < e.w;
    }
}roads[maxm];


bool cmp_w(const edge &e1, const edge &e2)
{
    return e1.w < e2.w;
}

edge greed[maxk];
int n, m, k;
ll d[maxn];

void input()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= m; i ++)
        cin >> roads[i].v >> roads[i].u >> roads[i].w;
    for (int i = 0; i < k; i ++)
        cin >> greed[i].v >> greed[i].u;
    for (int i = 1; i <= n; i ++)
        cin >> d[i];
}

int par[maxn];

int find_leader(int v)
{
    if (v == par[v])
        return v;
    return (par[v] = find_leader(par[v]));
}

bool unite(int v, int u)
{
    v = find_leader(v);
    u = find_leader(u);

    if (v == u)
        return false;
    par[u] = v;
    ///cout << "return true" << endl;
    return true;
}

vector < pair < int, int > > adj[maxn];
int used[maxn];

void dfs(int v, int p, int tag)
{
    used[v] = tag;
    for (pair < int, int > nb : adj[v])
    {
        if (nb.first == p)
            continue;
        dfs(nb.first, v, tag);
    }
}

ll sub[maxn], cost[maxk];
ll calc(int v, int p)
{
    sub[v] = d[v];
    ll res = 0;
    for (pair < int, int > nb : adj[v])
    {
        if (nb.first == p)
            continue;
        res += calc(nb.first, v);
        sub[v] += sub[nb.first];
        if (nb.second != -1)
        {
            res = res + sub[nb.first] * cost[nb.second];
        }
    }
    return res;
}
void brute_force()
{

    ll res = 0;
    for (int mask = 0; mask < (1 << k); mask ++)
    {

        for (int i = 1; i <= n; i ++)
        {
            par[i] = i;
            adj[i].clear();
        }

        bool done = false;
        for (int j = 0; j < k; j ++)
        {
            if ((mask & (1 << j)) == 0)
                continue;
            ///cout << find_leader(greed[j].v) << " : " << find_leader(greed[j].u) << endl;
            if (unite(greed[j].v, greed[j].u) == false)
            {

                done = true;
                break;
            }

            adj[greed[j].v].push_back({greed[j].u, j});
            adj[greed[j].u].push_back({greed[j].v, j});
        }

        if (done)
            continue;

        for (int i = 1; i <= m; i ++)
        {
            if (unite(roads[i].v, roads[i].u))
            {
                adj[roads[i].v].push_back({roads[i].u, - 1});
                adj[roads[i].u].push_back({roads[i].v, - 1});
            }
        }

        for (int j = 0; j < k; j ++)
        {
            if ((mask & (1 << j)) == 0)
                continue;
            for (int i = 1; i <= n; i ++)
                used[i] = 0;
            dfs(greed[j].v, greed[j].u, 1);
            dfs(greed[j].u, greed[j].v, 2);
            /**for (int i = 1; i <= n; i ++)
                cout << used[i] << " ";
            cout << endl;*/
            ll price = inf;
            for (int i = 1; i <= m; i ++)
            {
                if (used[roads[i].v] != used[roads[i].u])
                    price = min(price, roads[i].w);
            }
            ///cout << "price " << price << endl;
            cost[j] = price;
        }

        ll cur = calc(1, -1);
        res = max(res, cur);
    }

    cout << res << endl;
}


void preprocess()
{
    sort(roads + 1, roads + m + 1, cmp_w);
}
void solve()
{
    input();
    preprocess();
    brute_force();
}

int main()
{
    speed();
    solve();
    return 0;
}

/*
5 5 1
3 5 2
1 2 3
2 3 5
2 4 4
4 3 6
1 3
10 20 30 40 50

5 6 1
1 5 3
5 4 2
4 3 6
3 2 3
1 3 7
1 2 2
5 3
1 1 1 1 1
*/

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