1014-Computation of Minimum Length
全ての家を通るパイプを建設するのに必要な長さの最小値を求める程度の問題。
クラスカル法→貪欲に辺を消していく。
UnionFind木は蟻本参考にしました。
計算量はおそらくO(E^2)
実装(C++/UnionFind木省略)
#include <iostream> #include <vector> #include <algorithm> #include <set> using namespace std; struct edge{int u, v, cost;}; bool comp(const edge &e1,const edge &e2){ return e1.cost<e2.cost; } const int MAX_E=5000; edge es[MAX_E]; bool used[MAX_E]; int V,E; int kruskal(){ sort(es,es+E,comp); fill(used,used+E,false); UnionFind uf(V); int res=0; for(int i=0;i<E;i++){ edge e=es[i]; if(!uf.same(e.u,e.v)){ used[i]=true; uf.unite(e.u,e.v); res+=e.cost; } } return res; } int s,d; bool check(){ UnionFind uf(V); for(int i=0;i<E;i++){ if(used[i]){ uf.unite(es[i].v,es[i].u); } } set<int> ss; for(int i=0;i<s;i++){ ss.insert(uf.find(i)); } for(int i=s;i<V;i++){ if(ss.find(uf.find(i))==ss.end()){ return false; } } return true; } int main() { int t,ans; for(;;){ E=0; cin >> s >> d;if(!(s|d))break; for(int i=0;i<s;i++){ for(int j=0;j<d;j++){ cin >> t; if(t!=0){ es[E].u=i;es[E].v=j+s;es[E++].cost=t; } } } for(int i=0;i<d-1;i++){ for(int j=0;j<d-i-1;j++){ cin >> t; if(t!=0){ es[E].u=i+s;es[E].v=j+s+i+1;es[E++].cost=t; } } } V=s+d; ans=kruskal(); for(int i=E-1;i>=0;i--){ if(used[i]){ used[i]=false; if(check()){ ans-=es[i].cost; }else{ used[i]=true; } } } cout << ans << endl; } return 0; }