Submission #1807776

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
using Int = long long;

struct Kruskal{

  struct UnionFind{
    Int n;
    vector<Int> r,p;
    UnionFind(){}
    UnionFind(Int sz):n(sz),r(sz,1),p(sz,0){iota(p.begin(),p.end(),0);}
    Int find(Int x){
      return (x==p[x]?x:p[x]=find(p[x]));
    }
    bool same(Int x,Int y){
      return find(x)==find(y);
    }
    void unite(Int x,Int y){
      x=find(x);y=find(y);
      if(x==y) return;
      if(r[x]<r[y]) swap(x,y);
      r[x]+=r[y];
      p[y]=x;
    }
  };
  
  struct edge{
    Int from,to,cost;
    edge(){}
    edge(Int from,Int to,Int cost):from(from),to(to),cost(cost){}
    bool operator<(const edge& e) const{
      return cost<e.cost;
    }
  };

  Int n;
  vector<edge> edges;

  Kruskal(){}
  Kruskal(Int sz):n(sz){}
  
  void add_edge(Int u,Int v,Int c){
    edges.push_back(edge(u,v,c));
  }

  void input(Int m,Int offset=0){
    Int a,b,c;
    for(Int i=0;i<m;i++){
      cin>>a>>b>>c;
      add_edge(a+offset,b+offset,c);
    }
  }
  
  Int build(){
    sort(edges.begin(),edges.end());
    UnionFind uf(n+1);
    Int res=0;
    for(Int i=0;i<(Int)edges.size();i++){
      edge e=edges[i];
      if(!uf.same(e.from,e.to)){
	res+=e.cost;
	uf.unite(e.from,e.to);
      }
    }
    return res;
  }
};


signed main(){
  Int n,m;
  cin>>n>>m;
  Kruskal k(n);
  k.input(m,-1);
  auto es=k.edges;
  Int q;
  cin>>q;
  for(Int i=0;i<q;i++){
    Int s,t;
    cin>>s>>t;
    s--;t--;
    Kruskal p(n);
    p.edges=es;
    p.add_edge(s,t,0);
    cout<<p.build()<<endl;
  }
  return 0;
}

Submission Info

Judge Result