#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define x first
#define y second
#define ii pair<int,int>
int n,m,k;
vector<vector<int> >a;
const int M=1e5+7;
const int inf=1e9+7;
int num_child[M],trace[M],l[M];
struct DSU
{
vector<int>sz,trace;
int n;
DSU(int _n=0)
{
n=_n;
sz.assign(n+7,1);
trace.resize(n+7);
iota(trace.begin(),trace.end(),0);
}
int get_dsu(int x)
{
return trace[x]==x?x:(trace[x]=get_dsu(trace[x]));
}
bool check(int x,int y)
{
int u=get_dsu(x);
int v=get_dsu(y);
return u==v;
}
bool get(int x,int y)
{
int u=get_dsu(x);
int v=get_dsu(y);
if(u==v)return true;
if(sz[u]>sz[v])swap(u,v);
trace[u]=v;
sz[v]+=sz[u];
return false;
}
};
struct node
{
int x,y,cost;
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;
}
};
void dfs(int x,int cha)
{
trace[x]=cha;
l[x]=l[cha]+1;
for(auto node:a[x])
{
if(node!=cha)
{
dfs(node,x);
num_child[x]+=num_child[node];
}
}
}
int get_bit(int x,int y)
{
return x&(1<<y);
}
bool maximize(ll &a,ll b)
{
if(a<b)
{
a=b;
return true;
}
return false;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,m,k;
cin>>n>>m>>k;
vector<node>e;
vector<int>color(n+1);
for(int i=1;i<=m;i++)
{
int x,y,cost;
cin>>x>>y>>cost;
e.push_back({x,y,cost});
}
vector<node>mst;
sort(e.begin(),e.end());
DSU s(n);
for(auto node:e)
{
if(!s.check(node.x,node.y))
{
mst.push_back({node.x,node.y,node.cost});
}
}
s=DSU(n);
vector<ii>edge;
for(int i=1;i<=k;i++)
{
int x,y;
cin>>x>>y;
edge.push_back(make_pair(x,y));
s.get(x,y);
}
vector<node>need,basic;
for(auto node:mst)
{
if(!s.get(node.x,node.y))
{
need.push_back({node.x,node.y,node.cost});
}
else basic.push_back({node.x,node.y,node.cost});
}
for(int i=1;i<=n;i++)
{
cin>>color[i];
}
s=DSU(n);
for(auto node:need)
{
s.get(node.x,node.y);
}
vector<int>index(n+1);
int cnt=0;
for(int i=1;i<=n;i++)
{
if(s.get_dsu(i)!=i)continue;
index[i]=++cnt;
}
for(int i=1;i<=n;i++)
{
index[i]=index[s.get_dsu(i)];
}
vector<int>sum(cnt+1,0);
for(int i=1;i<=n;i++)
{
sum[index[i]]+=color[i];
}
a.resize(cnt+7);
int sz=(int)basic.size();
ll kq=0;
for(int mask=0;mask<(1<<k);mask++)
{
bool check=true;
s=DSU(cnt);
vector<bool>check_edge(sz,false);
for(int i=1;i<=cnt;i++)
{
a[i].clear();
num_child[i]=sum[i];
}
for(int i=0;i<k;i++)
{
if(!get_bit(mask,i))continue;
ii res=edge[i];
int u=index[res.x];
int v=index[res.y];
if(s.check(u,v))
{
check=false;
break;
}
s.get(u,v);
//cout<<u<<" "<<v<<"-----"<<endl;
a[u].push_back(v);
a[v].push_back(u);
}
if(!check)continue;
for(int i=0;i<sz;i++)
{
node res=basic[i];
int u=index[res.x];
int v=index[res.y];
if(s.check(u,v))continue;
else
{
s.get(u,v);
check_edge[i]=true;
a[u].push_back(v);
a[v].push_back(u);
}
}
//cout<<mask<<endl;
dfs(index[1],0);
vector<int>cp(sz+1);
for(int i=0;i<k;i++)
{
if(!get_bit(mask,i))continue;
ii node=edge[i];
int u=index[node.x];
int v=index[node.y];
if(trace[v]==u)swap(u,v);
cp[u]=inf;
}
for(int i=0;i<sz;i++)
{
if(!check_edge[i])continue;
node res=basic[i];
int u=index[res.x];
int v=index[res.y];
if(trace[v]==u)swap(u,v);
cp[u]=0;
}
for(int i=0;i<sz;i++)
{
if(check_edge[i])continue;
node res=basic[i];
int u=index[res.x];
int v=index[res.y];
if(l[u]>l[v])swap(u,v);
int cost=res.cost;
while(l[v]>l[u])
{
cp[v]=min(cp[v],cost);
v=trace[v];
}
while(v!=u)
{
cp[u]=min(cp[u],cost);
cp[v]=min(cp[v],cost);
u=trace[u];
v=trace[v];
}
}
ll ans=0;
for(int i=1;i<=cnt;i++)
{
ans+=1LL*cp[i]*num_child[i];
}
maximize(kq,ans);
}
cout<<kq;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
388 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
388 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
3 ms |
332 KB |
Output is correct |
| 4 |
Correct |
2 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
388 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
3 ms |
332 KB |
Output is correct |
| 4 |
Correct |
2 ms |
332 KB |
Output is correct |
| 5 |
Correct |
78 ms |
664 KB |
Output is correct |
| 6 |
Correct |
89 ms |
588 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
388 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
3 ms |
332 KB |
Output is correct |
| 4 |
Correct |
2 ms |
332 KB |
Output is correct |
| 5 |
Correct |
78 ms |
664 KB |
Output is correct |
| 6 |
Correct |
89 ms |
588 KB |
Output is correct |
| 7 |
Execution timed out |
2564 ms |
21520 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
388 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
3 ms |
332 KB |
Output is correct |
| 4 |
Correct |
2 ms |
332 KB |
Output is correct |
| 5 |
Correct |
78 ms |
664 KB |
Output is correct |
| 6 |
Correct |
89 ms |
588 KB |
Output is correct |
| 7 |
Execution timed out |
2564 ms |
21520 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
