Link
先让\(k\)条边的权值为\(0\)然后建出MST。
然后我们枚举非树边\((u,v,w)\)，，树上\(u,v\)间的路径上的边的边权都必需\(\le w\)。
这个操纵可以用并查集/树剖+线段树等数据布局维护。

#include<tuple> #include<cstdio> #include<cctype> #include<vector> #include<cstring> #include<utility> #include<iostream> #define pi pair<int,int> namespace IO { char ibuf[(1<<21)+1],*iS,*iT; char Get(){return (iS==iT? (iT=(iS=ibuf)+fread(ibuf,1,(1<<21)+1,stdin),(iS==iT? EOF:*iS++)):*iS++);} int read(){int x=0,c=Get();while(!isdigit(c))c=Get();while(isdigit(c))x=x*10+c-48,c=Get();return x;} } using IO::read; using std::fill; using std::pair; using std::tuple; using std::vector; using i64=long long; const int N=500007; vector<pi>e[N];vector<tuple<int,int,int>>E; int dep[N],p[N],fa[N]; void dfs(int u,int d){dep[u]=d;for(auto[v,f]:e[u])if(!dep[v])p[v]=u*f,dfs(v,d+1);} int find(int x){return fa[x]? fa[x]=find(fa[x]):x;} int main() { int n=read(),k=read(),m=read(),cnt=0;i64 ans=0; for(int i=1,u,v;i<=k;++i) u=read(),v=read(),e[u].emplace_back(v,1),e[v].emplace_back(u,1),fa[find(u)]=find(v); for(int i=1,u,v,fu,fv;i<=m;++i) if((fu=find(u=read()))^(fv=find(v=read()))) read(),e[u].emplace_back(v,-1),e[v].emplace_back(u,-1),fa[fu]=fv; else E.emplace_back(u,v,read()); dfs(1,1),memset(fa+1,0,n<<2); for(auto[u,v,w]:E) while((u=find(u))^(v=find(v))) { if(dep[u]<dep[v]) std::swap(u,v); if(p[u]>0) ++cnt,ans+=w; fa[u]=abs(p[u]); } cnt<k? puts("-1"):printf("%lld",ans); }

CF1023F Mobile Phone Network