#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define F first
#define S second
#define pii pair<int,int>
#define mpr make_pair
typedef long long ll;
const int maxn = 1e5+10;
const int mod = 1e9+7;
const ll inf = 1e9+10;
int n, m, k;
struct dsu
{
int par[maxn];
void f_reset() {memset(par, -1, sizeof par);}
void reset() {for(int i = 0; i <= 22; i++) par[i] = -1;}
int get_par(int v)
{
if(par[v] < 0) return v;
return par[v] = get_par(par[v]);
}
void add(int u, int v)
{
u = get_par(u);
v = get_par(v);
if(u == v) return;
if(par[u] < par[v]) swap(u,v);
par[v] += par[u];
par[u] = v;
}
bool ask(int u, int v) {return (get_par(u) == get_par(v));}
} dsu;
vector<int> T[maxn];
ll sz[maxn];
int par[maxn], num, comp[maxn], p[maxn];
bool mark[maxn];
void dfs(int v)
{
mark[v] = 1;
comp[v] = num; sz[num] += p[v];
for(auto u : T[v])
if(!mark[u]) dfs(u);
}
vector<int> Tree[25];
int pa[maxn], W[maxn];
ll stt[maxn];
void dfs_T(int v)
{
W[v] = inf;
stt[v] = sz[v];
for(auto u : Tree[v])
if(u != pa[v])
{
pa[u] = v;
dfs_T(u);
stt[v] += stt[u];
}
}
ll ans = 0;
void reset()
{
ans = 0;
dsu.reset();
for(int i = 0; i <= 22; i++)
{
Tree[i].clear();
W[i] = inf;
pa[i] = 0;
stt[i] = 0;
}
}
signed main()
{
//ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
scanf("%d%d%d", &n, &m, &k);
vector<pair<int,pii>> edge, Bedge; vector<pii> Redge;
for(int i = 1, u, v, c; i <= m; i++)
{
scanf("%d%d%d", &u, &v, &c);
edge.push_back({c,{u,v}});
}
sort(edge.begin(), edge.end());
dsu.f_reset();
vector<pair<int,pii>> mst;
for(auto e : edge)
{
int u = e.S.F, v = e.S.S;
if(!dsu.ask(u,v))
{
dsu.add(u,v);
mst.push_back(e);
}
}
dsu.f_reset();
for(int i = 1, u, v; i <= k; i++)
{
cin>> u >> v;
Redge.push_back({u,v});
dsu.add(u,v);
}
for(auto e : mst)
{
int u = e.S.F, v = e.S.S;
if(!dsu.ask(u,v))
{
T[u].push_back(v);
T[v].push_back(u);
dsu.add(u,v);
}
else Bedge.push_back(e); // Bedge mishe yalaye hazfi
}
for(int i = 1; i <= n; i++) scanf("%d", p+i);
// comp[Root = 1] = 1
for(int i = 1; i <= n; i++)
if(!mark[i])
{
num++;
dfs(i);
}
dsu.f_reset();
ll last_ans = 0;
for(int msk = 0; msk < (1<<k); msk++)
{
// in k ta dori nabashano ham bayad check koni
reset();
bool sw = 0;
for(int i = 0; i < k; i++)
if((1<<i) & msk)
{
int u = comp[Redge[i].F], v = comp[Redge[i].S];
if(dsu.ask(u,v)) {sw = 1; break;}
dsu.add(u,v);
Tree[u].push_back(v);
Tree[v].push_back(u);
}
if(sw) continue;
for(auto e : Bedge)
{
int u = comp[e.S.F], v = comp[e.S.S];
if(!dsu.ask(u,v))
{
dsu.add(u,v);
Tree[u].push_back(v);
Tree[v].push_back(u);
}
}
dfs_T(1);
for(auto e : Bedge)
{
int w = e.F; int u = comp[e.S.F], v = comp[e.S.S];
bool seen[num+2];
memset(seen, 0, sizeof seen);
while(u != 1)
{
(seen[u] ^= 1);
u = pa[u];
}
while(v != 1)
{
(seen[v] ^= 1);
v = pa[v];
}
for(int i = 1; i <= num; i++)
if(seen[i]) W[i] = min(W[i],w);
}
ans = 0;
for(int i = 0; i < k; i++)
if((1<<i) & msk)
{
int u = comp[Redge[i].F], v = comp[Redge[i].S];
if(u == pa[v]) ans += W[v] * stt[v];
if(v == pa[u]) ans += W[u] * stt[u];
}
last_ans = max(last_ans, ans);
}
printf("%lld", last_ans);
}
/*
5 5 2
1 5 1
1 2 2
2 3 2
3 4 1
4 5 2
2 4
2 5
1 1 1 1 1
*/
Compilation message
toll.cpp: In function 'int main()':
toll.cpp:92:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &n, &m, &k);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &u, &v, &c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:132:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i = 1; i <= n; i++) scanf("%d", p+i);
~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3072 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3072 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3072 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3072 KB |
Output is correct |
| 3 |
Correct |
3 ms |
3072 KB |
Output is correct |
| 4 |
Correct |
3 ms |
3072 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3072 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3072 KB |
Output is correct |
| 3 |
Correct |
3 ms |
3072 KB |
Output is correct |
| 4 |
Correct |
3 ms |
3072 KB |
Output is correct |
| 5 |
Correct |
5 ms |
3328 KB |
Output is correct |
| 6 |
Correct |
5 ms |
3328 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3072 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3072 KB |
Output is correct |
| 3 |
Correct |
3 ms |
3072 KB |
Output is correct |
| 4 |
Correct |
3 ms |
3072 KB |
Output is correct |
| 5 |
Correct |
5 ms |
3328 KB |
Output is correct |
| 6 |
Correct |
5 ms |
3328 KB |
Output is correct |
| 7 |
Correct |
257 ms |
11992 KB |
Output is correct |
| 8 |
Correct |
264 ms |
12136 KB |
Output is correct |
| 9 |
Correct |
282 ms |
11992 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3072 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3072 KB |
Output is correct |
| 3 |
Correct |
3 ms |
3072 KB |
Output is correct |
| 4 |
Correct |
3 ms |
3072 KB |
Output is correct |
| 5 |
Correct |
5 ms |
3328 KB |
Output is correct |
| 6 |
Correct |
5 ms |
3328 KB |
Output is correct |
| 7 |
Correct |
257 ms |
11992 KB |
Output is correct |
| 8 |
Correct |
264 ms |
12136 KB |
Output is correct |
| 9 |
Correct |
282 ms |
11992 KB |
Output is correct |
| 10 |
Correct |
2116 ms |
12036 KB |
Output is correct |
| 11 |
Execution timed out |
2582 ms |
11992 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
