#include "bits/stdc++.h"
#define ll long long
#define ff first
#define ss second
#define edgew pair<int, pair<int,int> >
#define edge pair<int,int>
using namespace std;
struct connectivity{
vector<int> ata;
vector<int> sz;
int n;
connectivity(int _n){
n = _n;
ata.resize(n+1);
sz.resize(n+1);
}
void init(){
for (int i = 1; i <= n; i++)
ata[i] = i, sz[i] = 1;
}
int tap(int x){
if (ata[x] == x)
return x;
return ata[x] = tap(ata[x]);
}
bool merge(int x, int y){
if ((x=tap(x)) == (y=tap(y)))
return 0;
if (sz[x] < sz[y])
swap(x, y);
ata[y] = x;
sz[x] += sz[y];
return 1;
}
bool is_connected(int x, int y){
return tap(x) == tap(y);
}
vector<int> get_components(){
vector<int> components;
for (int i = 1; i <= n; i++)
if (ata[i] == i)
components.push_back(i);
return components;
}
};
const int N = 1e5+5;
const int K = 20;
const int INF = 1e9;
edgew black_edges[N];
edge blue_edges[K];
int a[N];
vector<int> adj[N];
void add_edge(int u, int v){
adj[u].push_back(v);
adj[v].push_back(u);
}
ll sub[N];
int par[N], lvl[N], l[N];
void dfs(int nd, int pr){
par[nd] = pr;
sub[nd] = a[nd];
for (auto to: adj[nd])
if (to != pr){
lvl[to] = lvl[nd]+1;
dfs(to, nd);
sub[nd] += sub[to];
}
}
void upd(int u, int v, int w){
while (u != v){
if (lvl[u] > lvl[v])
swap(u, v);
l[v] = min(l[v], w);
v = par[v];
}
}
int main(){
// freopen("file.in", "r", stdin);
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= m; i++){
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
black_edges[i] = {w, {u, v}};
}
sort(black_edges+1, black_edges+m+1);
connectivity dsu(n);
dsu.init();
// black edges
vector<edgew> selected;
for (int i = 1; i <= m; i++){
int w = black_edges[i].ff;
int u = black_edges[i].ss.ff;
int v = black_edges[i].ss.ss;
if (dsu.merge(u, v))
selected.push_back(black_edges[i]);
}
for (int i = 0; i < k; i++){
int u, v;
scanf("%d%d", &u, &v);
blue_edges[i] = {u, v};
}
for (int i = 1; i <= n; i++)
scanf("%d", a+i);
ll ans = 0;
//O(2^k*nlogn)
for (int mask = 0; mask < (1<<k); mask++){
dsu.init();
for (int i = 1; i <= n; i++)
adj[i].clear(), l[i] = INF;
bool valid = true;
for (int i = 0; i < k; i++)
if (mask>>i&1){
auto [u, v] = blue_edges[i];
add_edge(u, v);
if (!dsu.merge(u, v))
valid = false;
}
if (!valid)
continue;
vector<bool> state(selected.size(), 0);
for (int i = 0; i < selected.size(); i++){
int u = selected[i].ss.ff;
int v = selected[i].ss.ss;
state[i] = dsu.merge(u, v);
if (state[i])
add_edge(u, v);
}
dfs(1, -1);
for (int i = 0; i < selected.size(); i++){
int w = selected[i].ff;
int u = selected[i].ss.ff;
int v = selected[i].ss.ss;
if (!state[i])
upd(u, v, w);
}
ll value = 0;
for (int i = 0; i < k; i++)
if (mask>>i&1){
auto [u, v] = blue_edges[i];
add_edge(u, v);
if (lvl[u] > lvl[v])
swap(u, v);
value += l[v] * sub[v];
}
ans = max(ans, value);
}
printf("%lld\n", ans);
}
Compilation message (stderr)
toll.cpp: In function 'int main()':
toll.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
82 | scanf("%d%d%d", &n, &m, &k);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:85:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
85 | scanf("%d%d%d", &u, &v, &w);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:102:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
102 | scanf("%d%d", &u, &v);
| ~~~~~^~~~~~~~~~~~~~~~
toll.cpp:106:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
106 | scanf("%d", a+i);
| ~~~~~^~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |