#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define pb push_back
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(),v.end()
using namespace std;
mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }
const int N = 3e5 + 2;
const int Mod = 1e9 + 7;
const int INF = 2e9 + 7;
const ll BASE = 137;
const int szBL = 320;
struct Disjoin_set {
int lab[N], sz[N];
void init (int n ){
rep (i, 1, n) lab[i] = i, sz[i] = 1;
}
int Find (int u) {
return u == lab[u] ? u : lab[u] = Find(lab[u]);
}
bool Join (int u, int v) {
if ((u = Find(u)) == (v = Find(v))) return 0;
if (sz[u] < sz[v]) swap(u, v);
sz[u] += sz[v];
lab[v] = u;
return 1;
}
}DSU;
struct Edge {
int u, v, w, id;
};
int n, m, K;
int P[N];
pii nroad[N];
vector<int> ke[N], adj[N];
vector<Edge> delE;
bool inE[N];
ll cnt[N];
int num_cpn, cpn[N];
int mn[N], dd[N], dp[N];
int high[N], par[N];
void solution () {
cin >> n >> m >> K;
vector<Edge> edges;
rep (i, 1, m) {
int u, v, w;
cin >> u >> v >> w;
edges.pb({u, v, w, i});
}
DSU.init(n);
sort (ALL(edges), [] (Edge u, Edge v) { return u.w < v.w; });
ll MST = 0;
iter (&E, edges)
if (DSU.Join(E.u, E.v)) inE[E.id] = 1;
rep (i, 1, K) cin >> nroad[i].fs >> nroad[i].se;
rep (i, 1, n) cin >> P[i];
DSU.init(n);
rep (i, 1, K) {
DSU.Join(nroad[i].fs, nroad[i].se);
}
iter (&E, edges) if (DSU.Join(E.u, E.v) == 0) {
delE.pb(E);
inE[E.id] = 0;
}
iter (&E, edges) if (inE[E.id] == 1) {
ke[E.u].pb(E.v);
ke[E.v].pb(E.u);
}
function<void(int, int)> pdfs = [&] (int u, int p) {
cnt[num_cpn] += P[u];
cpn[u] = num_cpn;
iter (&v, ke[u]) {
if (v == p) continue;
pdfs (v, u);
}
};
rep (i, 1, n) {
if (cpn[i]) continue;
++num_cpn;
pdfs(i, 0);
}
rep (i, 1, K) {
nroad[i].fs = cpn[nroad[i].fs];
nroad[i].se = cpn[nroad[i].se];
}
iter (&E, delE) {
E.u = cpn[E.u];
E.v = cpn[E.v];
}
ll res = 0;
function<void(int)> solve = [&] (int msk) {
DSU.init(num_cpn);
rep (i, 1, num_cpn) vector<int> ().swap(adj[i]), mn[i] = INF, dd[i] = 0, dp[i] = 0;
rep (i, 1, K) if (bit(msk, i - 1)) {
if (DSU.Join(nroad[i].fs, nroad[i].se) == 0) return;
adj[nroad[i].fs].pb(nroad[i].se);
adj[nroad[i].se].pb(nroad[i].fs);
}
static vector<Edge> curE; vector<Edge> ().swap(curE);
iter (&E, delE) {
if (DSU.Join (E.u, E.v) == 0) curE.pb(E);
else {
adj[E.u].pb(E.v);
adj[E.v].pb(E.u);
}
}
function<void(int, int)> pdfs2 = [&] (int u, int p) {
high[u] = high[p] + 1;
par[u] = p;
iter (&v, adj[u]) if (v != p) pdfs2 (v, u);
};
pdfs2 (1, 0);
iter (&E, curE) {
int u = E.u, v = E.v, val = E.w;
while (u != v) {
if (high[u] > high[v]) swap(u, v);
mn[v] = min(mn[v], val);
v = par[v];
}
}
rep (i, 1, K) if (bit(msk, i - 1)) {
if (high[nroad[i].fs] > high[nroad[i].se]) swap(nroad[i].fs, nroad[i].se);
dd[nroad[i].se] = 1;
}
ll curcost = 0;
function<void(int,int)> dfs2 = [&] (int u, int p) {
dp[u] = cnt[u];
iter (&v, adj[u]) {
if (v == p) continue;
dfs2 (v, u);
dp[u] += dp[v];
if (dd[v]) {
curcost += 1LL * mn[v] * dp[v];
}
}
};
dfs2(1, 0);
res = max(res, curcost);
};
rep (msk, 1, (1 << K) - 1) solve(msk);
cout << res <<"\n";
}
#define file(name) freopen(name".inp","r",stdin); \
freopen(name".out","w",stdout);
int main () {
// file("c");
ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
int num_Test = 1;
// cin >> num_Test;
while (num_Test--)
solution();
}
/*
no bug challenge +2
2 + 8 * 2 - 9
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
*/
Compilation message
toll.cpp: In lambda function:
toll.cpp:114:38: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
114 | rep (i, 1, K) if (bit(msk, i - 1)) {
| ~~^~~
toll.cpp:10:30: note: in definition of macro 'bit'
10 | #define bit(msk, i) ((msk >> i) & 1)
| ^
toll.cpp:141:38: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
141 | rep (i, 1, K) if (bit(msk, i - 1)) {
| ~~^~~
toll.cpp:10:30: note: in definition of macro 'bit'
10 | #define bit(msk, i) ((msk >> i) & 1)
| ^
toll.cpp: In function 'void solution()':
toll.cpp:72:8: warning: unused variable 'MST' [-Wunused-variable]
72 | ll MST = 0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
24924 KB |
Output is correct |
| 2 |
Correct |
3 ms |
24924 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
24924 KB |
Output is correct |
| 2 |
Correct |
3 ms |
24924 KB |
Output is correct |
| 3 |
Correct |
6 ms |
24924 KB |
Output is correct |
| 4 |
Correct |
4 ms |
24924 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
24924 KB |
Output is correct |
| 2 |
Correct |
3 ms |
24924 KB |
Output is correct |
| 3 |
Correct |
6 ms |
24924 KB |
Output is correct |
| 4 |
Correct |
4 ms |
24924 KB |
Output is correct |
| 5 |
Correct |
49 ms |
25432 KB |
Output is correct |
| 6 |
Correct |
56 ms |
25180 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
24924 KB |
Output is correct |
| 2 |
Correct |
3 ms |
24924 KB |
Output is correct |
| 3 |
Correct |
6 ms |
24924 KB |
Output is correct |
| 4 |
Correct |
4 ms |
24924 KB |
Output is correct |
| 5 |
Correct |
49 ms |
25432 KB |
Output is correct |
| 6 |
Correct |
56 ms |
25180 KB |
Output is correct |
| 7 |
Execution timed out |
2532 ms |
45432 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
24924 KB |
Output is correct |
| 2 |
Correct |
3 ms |
24924 KB |
Output is correct |
| 3 |
Correct |
6 ms |
24924 KB |
Output is correct |
| 4 |
Correct |
4 ms |
24924 KB |
Output is correct |
| 5 |
Correct |
49 ms |
25432 KB |
Output is correct |
| 6 |
Correct |
56 ms |
25180 KB |
Output is correct |
| 7 |
Execution timed out |
2532 ms |
45432 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
