#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);
}
vector < int > graph[maxn];
int marked[maxn];
ll population[maxn];
void trav(int v, int p, int s)
{
marked[v] = s;
population[s] += d[v];
for (int u : graph[v])
{
if (u == p)
continue;
trav(u, v, s);
}
}
vector < edge > maybe;
void compress_tree()
{
for (int i = 1; i <= n; i ++)
{
par[i] = i;
}
for (int i = 0; i < k; i ++)
{
unite(greed[i].v, greed[i].u);
}
for (int i = 1; i <= m; i ++)
{
if (unite(roads[i].v, roads[i].u))
{
maybe.push_back(roads[i]);
graph[roads[i].v].push_back(roads[i].u);
graph[roads[i].u].push_back(roads[i].v);
}
}
int cp_cnt = 0;
for (int i = 1; i <= n; i ++)
{
if (!marked[i])
{
cp_cnt ++;
trav(i, -1, cp_cnt);
}
}
vector < edge > fin;
for (int i = 1; i <= m; i ++)
{
edge cur = roads[i];
if (marked[cur.v] != marked[cur.u])
fin.push_back(edge(marked[cur.v], marked[cur.u], cur.w));
}
for (int i = 0; i < k; i ++)
{
greed[i].v = marked[greed[i].v];
greed[i].u = marked[greed[i].u];
}
n = cp_cnt;
for (int i = 1; i <= n; i ++)
d[i] = population[i];
for (int i = 0; i < fin.size(); i ++)
{
roads[i + 1] = fin[i];
}
m = fin.size();
//cout << "new n " << n << endl;
//cout << "new m " << m << endl;
/**for (int i = 1; i <= n; i ++)
cout << d[i] << " ";
cout << endl;*/
}
void solve()
{
input();
preprocess();
compress_tree();
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
*/
Compilation message
toll.cpp: In function 'void compress_tree()':
toll.cpp:247:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
247 | for (int i = 0; i < fin.size(); i ++)
| ~~^~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
13148 KB |
Output is correct |
| 2 |
Correct |
2 ms |
13148 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
13148 KB |
Output is correct |
| 2 |
Correct |
2 ms |
13148 KB |
Output is correct |
| 3 |
Correct |
4 ms |
13148 KB |
Output is correct |
| 4 |
Correct |
4 ms |
13148 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
13148 KB |
Output is correct |
| 2 |
Correct |
2 ms |
13148 KB |
Output is correct |
| 3 |
Correct |
4 ms |
13148 KB |
Output is correct |
| 4 |
Correct |
4 ms |
13148 KB |
Output is correct |
| 5 |
Correct |
17 ms |
13144 KB |
Output is correct |
| 6 |
Correct |
45 ms |
13148 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
13148 KB |
Output is correct |
| 2 |
Correct |
2 ms |
13148 KB |
Output is correct |
| 3 |
Correct |
4 ms |
13148 KB |
Output is correct |
| 4 |
Correct |
4 ms |
13148 KB |
Output is correct |
| 5 |
Correct |
17 ms |
13144 KB |
Output is correct |
| 6 |
Correct |
45 ms |
13148 KB |
Output is correct |
| 7 |
Execution timed out |
2525 ms |
18880 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
13148 KB |
Output is correct |
| 2 |
Correct |
2 ms |
13148 KB |
Output is correct |
| 3 |
Correct |
4 ms |
13148 KB |
Output is correct |
| 4 |
Correct |
4 ms |
13148 KB |
Output is correct |
| 5 |
Correct |
17 ms |
13144 KB |
Output is correct |
| 6 |
Correct |
45 ms |
13148 KB |
Output is correct |
| 7 |
Execution timed out |
2525 ms |
18880 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
