#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define x first
#define y second
#define ii pair<int,int>
const int inf=1e9+7;
const int M=1e4+7;
int high[M],trace[M],cost[M];
vector<vector<ii> >used;
struct node
{
int x,y,cost;
bool check=false,need=false;
node(int _x=0,int _y=0,int _cost=0)
{
x=_x,y=_y,cost=_cost;
}
bool operator<(const node &a)const
{
return cost<a.cost;
}
};
struct DSU
{
int n;
vector<int>trace,sz;
DSU(int _n=0)
{
n=_n;
trace.resize(n+7);
sz.assign(n+7,1);
iota(trace.begin(),trace.end(),0);
}
int find_dsu(int x)
{
return trace[x]==x?trace[x]:find_dsu(trace[x]);
}
bool check(int x,int y)
{
return find_dsu(x)==find_dsu(y);
}
void get(int x,int y)
{
int u=find_dsu(x);
int v=find_dsu(y);
if(u==v)return ;
if(sz[u]>sz[v])swap(u,v);
trace[u]=v;
sz[v]+=sz[u];
}
void re()
{
for(int i=1;i<=n;i++)trace[i]=i;
}
};
int n,m,k;
void dfs(int x,int cha)
{
for(ii u:used[x])
{
int node=u.x;
int value=u.y;
if(node==cha)continue;
high[node]=high[x]+1;
cost[node]=value;
trace[node]=x;
dfs(node,x);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>k;
vector<node>edge(m+1);
for(int i=1;i<=m;i++)
{
int x,y,cost;
cin>>x>>y>>cost;
edge[i]={x,y,cost};
}
sort(edge.begin(),edge.end());
vector<ii>a(k+1);
for(int i=1;i<=k;i++)
{
int x,y;
cin>>x>>y;
a[i]=make_pair(x,y);
}
DSU s(n);
vector<int>color(n+1);
for(int i=1;i<=n;i++)
{
cin>>color[i];
}
for(int i=1;i<=m;i++)
{
if(!s.check(edge[i].x,edge[i].y))
{
edge[i].check=true;
s.get(edge[i].x,edge[i].y);
}
}
s.re();
for(int i=1;i<=k;i++)
{
if(!s.check(a[i].x,a[i].y))
{
s.get(a[i].x,a[i].y);
}
}
vector<int>save;
for(int i=1;i<=m;i++)
{
if(!s.check(edge[i].x,edge[i].y))
{
s.get(edge[i].x,edge[i].y);
edge[i].need=true;
}
}
for(int i=1;i<=m;i++)
{
if(edge[i].check&&!edge[i].need)
{
save.push_back(i);
}
}
s.re();
for(int i=1;i<=m;i++)
{
if(edge[i].need)
{
s.get(edge[i].x,edge[i].y);
}
}
int num_color=0;
vector<int>value(n+1);
for(int i=1;i<=n;i++)
{
if(s.find_dsu(i)!=i)continue;
value[i]=++num_color;
}
vector<int>num_child(num_color+1);
for(int i=1;i<=n;i++)
{
int x=s.find_dsu(i);
num_child[value[x]]+=color[i];
}
for(int i=1;i<=k;i++)
{
int x=s.find_dsu(a[i].x);
int y=s.find_dsu(a[i].y);
a[i].x=value[x];
a[i].y=value[y];
}
for(int node:save)
{
int x=s.find_dsu(edge[node].x);
int y=s.find_dsu(edge[node].y);
edge[node].x=value[x];
edge[node].y=value[y];
}
DSU dsu(num_color);
used.resize(num_color+1);
int ans=0;
for(int mask=0;mask<(1<<k);mask++)
{
dsu.re();
for(int i=1;i<=num_color;i++)used.clear();
for(int i=1;i<=num_color;i++)high[i]=0;
bool check=false;
for(int i=1;i<=k;i++)
{
if(!((mask>>(i-1))&1))continue;
if(dsu.check(a[i].x,a[i].y))check=true;
dsu.get(a[i].x,a[i].y);
used[a[i].x].push_back({a[i].y,inf});
used[a[i].y].push_back({a[i].x,inf});
}
if(check)continue;
vector<int>solve;
for(int node:save)
{
int x=edge[node].x;
int y=edge[node].y;
if(dsu.check(x,y))
{
solve.push_back(node);
continue;
}
dsu.check(x,y);
used[x].push_back({y,0});
used[y].push_back({x,0});
}
dfs(1,0);
for(int node:solve)
{
int x=edge[node].x;
int y=edge[node].y;
int value=edge[node].cost;
if(high[x]>high[y])swap(x,y);
while(high[y]>high[x])
{
cost[y]=min(cost[y],value);
y=trace[y];
}
while(x!=y)
{
cost[x]=min(cost[x],value);
cost[y]=min(cost[y],value);
x=trace[x];
y=trace[y];
}
}
int sum=0;
for(int i=2;i<=num_color;i++)
{
sum+=cost[i]*num_child[i];
}
ans=max(ans,sum);
}
cout<<ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
