1 条题解

  • 0
    @ 2026-5-5 16:48:45
    #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
    上传者