#include <iostream>
#include <vector>
#include <algorithm>
#include <vector>
#define int long long
using namespace std;
struct edge{
int u,v,w;
}e[100001],r[21];
const int inf=1e9;
int n,m,k,p[100001],l[100001],sz[100001],pre[100001],ch[100001],par[100001],d[100001],val[100001],res;
vector <edge> ve,v2,v3;
vector <int> ke[100001],nodes;
int f(int i){
return (l[i]==i?i:l[i]=f(l[i]));
}
void unite(int i, int j){
i=f(i);
j=f(j);
if (sz[i]>sz[j])
swap(i,j);
l[j]=i;
sz[i]+=sz[j];
}
void prep(){
for (int i:nodes){
l[i]=pre[i];
sz[i]=p[i];
}
}
bool operator <(edge a, edge b){
return a.w<b.w;
}
void dfs(int u, int parent){
sz[u]=p[u];
for (int v:ke[u])
if (v!=parent){
d[v]=d[u]+1;
par[v]=u;
dfs(v,u);
sz[u]+=sz[v];
}
}
int calc(int mask){
prep();
for (int i:nodes){
ke[i].clear();
val[i]=inf;
}
for (int i=0;i<k;i++){
r[i].w=inf;
if ((mask>>i)&1){
if (f(r[i].u)==f(r[i].v))
return 0;
unite(r[i].u,r[i].v);
ke[r[i].u].push_back(r[i].v);
ke[r[i].v].push_back(r[i].u);
}
}
for (int i=0;i<ve.size();i++){
if (f(ve[i].u)==f(ve[i].v)){
ch[i]=0;
continue;
}
ch[i]=1;
unite(ve[i].u,ve[i].v);
ke[ve[i].u].push_back(ve[i].v);
ke[ve[i].v].push_back(ve[i].u);
}
int root=f(1);
d[root]=0;
dfs(root,root);
for (int i=0;i<ve.size();i++){
if (ch[i])
continue;
int u=ve[i].u,v=ve[i].v;
if (d[u]<d[v])
swap(u,v);
while (d[u]>d[v]){
val[u]=min(val[u],ve[i].w);
u=par[u];
}
while (u!=v){
val[u]=min(val[u],ve[i].w);
val[v]=min(val[v],ve[i].w);
u=par[u];
v=par[v];
}
}
int res=0;
for (int i=0;i<k;i++)
if ((mask>>i)&1){
int u=r[i].u,v=r[i].v;
if (u==par[v])
swap(u,v);
res+=sz[u]*val[u];
}
return res;
}
signed main(){
ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
cin >> n >> m >> k;
for (int i=0;i<m;i++)
cin >> e[i].u >> e[i].v >> e[i].w;
for (int i=0;i<k;i++)
cin >> r[i].u >> r[i].v;
for (int i=1;i<=n;i++){
cin >> p[i];
pre[i]=i;
nodes.push_back(i);
}
prep();
sort(e,e+m);
for (int i=0;i<m;i++){
if (f(e[i].u)==f(e[i].v))
continue;
unite(e[i].u,e[i].v);
ve.push_back(e[i]);
}
prep();
for (int i=0;i<k;i++)
unite(r[i].u,r[i].v);
for (auto i:ve){
if (f(i.u)==f(i.v))
continue;
unite(i.u,i.v);
v2.push_back(i);
}
prep();
for (auto i:v2)
unite(i.u,i.v);
for (auto &i:ve)
i={f(i.u),f(i.v),i.w};
for (auto &i:v2)
i={f(i.u),f(i.v),i.w};
for (int i=0;i<k;i++)
r[i]={f(r[i].u),f(r[i].v),inf};
nodes.clear();
for (int i=1;i<=n;i++){
pre[i]=f(i);
p[i]=sz[i];
if (i==pre[i])
nodes.push_back(i);
}
prep();
for (auto i:ve){
if (f(i.u)==f(i.v))
continue;
unite(i.u,i.v);
v3.push_back(i);
}
swap(ve,v3);
for (int i=0;i<(1<<k);i++)
res=max(res,calc(i));
cout << res;
}
Compilation message
toll.cpp: In function 'long long int calc(long long int)':
toll.cpp:60:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for (int i=0;i<ve.size();i++){
| ~^~~~~~~~~~
toll.cpp:73:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for (int i=0;i<ve.size();i++){
| ~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
