#include <bits/stdc++.h>
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")
using namespace std;
using ll = long long;
using ld = long double;
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lb lower_bound
#define int ll
const int MOD = 998244353;
int N, M, K, P[100005], par[100005];
int calc[100005], dep[100005], anc[100005], nat[100005];
int Key[100005], val[100005];
vector<int> A, B, C, X, Y;
vector<int> adj[100005];
vector<pair<int, int>> G[100005];
bool compare(int u, int v) {
return C[u] < C[v];
}
int findSet(int v) {
if(par[v] == v) return v;
return par[v] = findSet(par[v]);
}
bool unionSet(int u, int v) {
u = findSet(u), v = findSet(v);
if(u == v) return 0;
par[u] = v; return 1;
}
void dfs(int v, int id) {
Key[v] = id; val[id] += P[v];
for(auto u : adj[v]) {
if(Key[u] == -1) dfs(u, id);
}
}
void DFS(int v, int p) {
calc[v] = val[v]; dep[v] = dep[p] + 1;
anc[v] = p;
for(auto u : G[v]) {
if(u.first == p) continue;
nat[u.first] = u.second;
DFS(u.first, v); calc[v] += calc[u.first];
}
}
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N >> M >> K;
A.resize(M), B.resize(M), C.resize(M);
for(int l = 0; l < M; l++) {
cin >> A[l] >> B[l] >> C[l];
--A[l], --B[l];
}
X.resize(K), Y.resize(K);
for(int l = 0; l < K; l++) {
cin >> X[l] >> Y[l];
--X[l], --Y[l];
}
for(int l = 0; l < N; l++) cin >> P[l];
vector<int> edges(M);
iota(edges.begin(), edges.end(), 0);
sort(edges.begin(), edges.end(), compare);
for(int l = 0; l < N; l++) par[l] = l;
vector<int> _A, _B, _C;
for(auto u : edges) {
if(unionSet(A[u], B[u])) {
_A.push_back(A[u]);
_B.push_back(B[u]);
_C.push_back(C[u]);
}
}
swap(A, _A), swap(B, _B), swap(C, _C);
M = A.size();
for(int l = 0; l < N; l++) par[l] = l;
for(int l = 0; l < K; l++) {
unionSet(X[l], Y[l]);
}
vector<array<int, 3>> E;
for(int l = 0; l < M; l++) {
if(unionSet(A[l], B[l])) {
adj[A[l]].push_back(B[l]);
adj[B[l]].push_back(A[l]);
}
else E.push_back({A[l], B[l], C[l]});
}
int cur = 0; memset(Key, -1, sizeof Key);
for(int l = 0; l < N; l++) {
if(Key[l] == -1) {
dfs(l, cur); ++cur;
}
}
for(int l = 0; l < K; l++) {
X[l] = Key[X[l]];
Y[l] = Key[Y[l]];
}
for(auto& u : E) {
u[0] = Key[u[0]];
u[1] = Key[u[1]];
}
int res = 0;
for(int l = 1; l < (1 << K); l++) {
for(int i = 0; i < cur; i++)
par[i] = i;
bool ok = 1;
for(int i = 0; i < K; i++) {
if(l & (1 << i))
ok &= unionSet(X[i], Y[i]);
}
if(!ok) continue;
for(int i = 0; i < cur; i++) G[i].clear();
for(int i = 0; i < K; i++) {
if(l & (1 << i)) {
G[X[i]].push_back({Y[i], 1});
G[Y[i]].push_back({X[i], 1});
}
}
vector<array<int, 3>> Q;
for(auto u : E) {
if(!unionSet(u[0], u[1]))
Q.push_back(u);
else {
G[u[0]].push_back({u[1], 0});
G[u[1]].push_back({u[0], 0});
}
}
DFS(0, 0); vector<int> arr(cur, 1e9);
for(auto q : Q) {
int u = q[0], v = q[1], w = q[2];
if(dep[u] < dep[v]) swap(u, v);
while(dep[u] > dep[v]) {
arr[u] = min(arr[u], w);
u = anc[u];
}
while(u != v) {
arr[u] = min(arr[u], w);
arr[v] = min(arr[v], w);
u = anc[u]; v = anc[v];
}
}
int ans = 0;
for(int i = 0; i < cur; i++) {
ans += calc[i] * arr[i] * nat[i];
}
res = max(res, ans);
}
cout << res << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5844 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5716 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5844 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5716 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5792 KB |
Output is correct |
| 4 |
Correct |
4 ms |
5844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5844 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5716 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5792 KB |
Output is correct |
| 4 |
Correct |
4 ms |
5844 KB |
Output is correct |
| 5 |
Correct |
5 ms |
6120 KB |
Output is correct |
| 6 |
Correct |
5 ms |
6100 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5844 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5716 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5792 KB |
Output is correct |
| 4 |
Correct |
4 ms |
5844 KB |
Output is correct |
| 5 |
Correct |
5 ms |
6120 KB |
Output is correct |
| 6 |
Correct |
5 ms |
6100 KB |
Output is correct |
| 7 |
Correct |
226 ms |
28368 KB |
Output is correct |
| 8 |
Correct |
247 ms |
25972 KB |
Output is correct |
| 9 |
Correct |
245 ms |
26180 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5844 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5716 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5792 KB |
Output is correct |
| 4 |
Correct |
4 ms |
5844 KB |
Output is correct |
| 5 |
Correct |
5 ms |
6120 KB |
Output is correct |
| 6 |
Correct |
5 ms |
6100 KB |
Output is correct |
| 7 |
Correct |
226 ms |
28368 KB |
Output is correct |
| 8 |
Correct |
247 ms |
25972 KB |
Output is correct |
| 9 |
Correct |
245 ms |
26180 KB |
Output is correct |
| 10 |
Correct |
1325 ms |
26008 KB |
Output is correct |
| 11 |
Correct |
1697 ms |
26060 KB |
Output is correct |
| 12 |
Correct |
1672 ms |
26076 KB |
Output is correct |
