1 条题解
-
0
#include <bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i=(a);i<(b);i++) const int maxn=5e5+5; int n,k,m,u,v,w,f[maxn],d[maxn]; array<int,2> p[maxn]; vector<array<int,2> > ady[maxn]; vector<array<int,3> > e; long long cst; int find(int x) {return f[x]==x?x:f[x]=find(f[x]); } void dfs(int x) { for(auto [y,w]:ady[x]) if(y!=p[x][0]) { p[y]={x,w}; d[y]=d[x]+1; dfs(y); } } void ae(int x, int y, int w) { ady[x].push_back({y,w}); ady[y].push_back({x,w}); } int main(){ ios_base::sync_with_stdio(0); cin>>n>>k>>m; rep(i,1,n+1) f[i]=i; rep(i,0,k) { cin>>u>>v; ae(u,v,0); f[find(u)]=find(v); } rep(i,0,m) { cin>>u>>v>>w; if(find(u)!=find(v)) f[f[u]]=f[v], ae(u,v,w); else e.push_back({u,v,w}); } dfs(1); rep(i,1,n+1) f[i]=i; for(auto [u,v,w]: e) { u=find(u),v=find(v); while(u!=v) { if(d[u]<d[v]) swap(u,v); auto [pu,w2] = p[u]; if(!w2) cst+=w, k--; u=f[u]=find(pu); } } cout<<(k?-1:cst)<<"\n"; }
- 1
信息
- ID
- 6845
- 时间
- 3000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 2
- 已通过
- 1
- 上传者