POJ 1258,2031
どちらも最小全域木を求める。
なんとなく、クラスカル法のほうが簡単な気がするのでそちらを採用することにする。
1258
#include <iostream> #include <cstdio> #include <iomanip> #include <vector> #include <map> #include <set> #include <queue> #include <bitset> #include <stack> #include <utility> #include <numeric> #include <algorithm> #include <functional> #include <cctype> #include <complex> #include <string> #include <sstream> using namespace std; #define all(c) c.begin(),c.end() #define rall(c) c.rbegin(),c.rend() #define rep(i,n) for(int i=0;i<(n);i++) #define tr(it,container) for(typeof(container.begin()) it = container.begin(); \ it != container.end(); ++it) #define mp(a,b) make_pair((a),(b)) #define eq == typedef long long ll; typedef complex<double> point; typedef pair<int,int> pii; // →↑←↓ const int dx[] = {1,0,-1,0}; const int dy[] = {0,-1,0,1}; const double EPS = 1e-9; const int INF = 10000000; int main(){ int N; while(cin >> N){ vector<vector<int> > M(N,vector<int>(N)); rep(i,N) rep(j,N) cin >> M[i][j]; vector<char> used(N,false); ll ret = 0; // cost , where. priority_queue<pii,vector<pii>,greater<pii> > Q; Q.push(mp(0,0)); while(!Q.empty()){ int cost = Q.top().first; int where = Q.top().second; Q.pop(); if(used[where]) continue; used[where] = true; ret += cost; for(int i=0;i<N;i++){ Q.push(mp(M[where][i],i)); } } cout << ret << endl; } return 0; }
2031
#include <iostream> #include <cstdio> #include <iomanip> #include <vector> #include <map> #include <set> #include <queue> #include <bitset> #include <stack> #include <utility> #include <numeric> #include <algorithm> #include <functional> #include <cctype> #include <complex> #include <string> #include <sstream> using namespace std; struct Station{ double x,y,z,r; Station(double x,double y,double z,double r) : x(x),y(y),z(z),r(r) {}; }; double square(double x){ return x*x; } double dist(const Station &a,const Station &b){ double dis = sqrt(square(a.x-b.x) + square(a.y-b.y) + square(a.z-b.z)) - (a.r + b.r); if(dis <= 0){ dis = 0; } return dis; }; int main(){ cout << setprecision(3) << fixed; while(true){ int n; cin >> n; if(n == 0) break; vector<Station> V; for(int _=0;_<n;_++){ double x,y,z,r; cin >> x >> y >> z >> r; V.push_back(Station(x,y,z,r)); } vector<vector<double> > D(n,vector<double>(n,0)); for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ D[i][j] = dist(V[i],V[j]); } } double ret = 0; vector<char> used(n,false); // cost where typedef pair<double,int> pdi; priority_queue<pdi,vector<pdi>,greater<pdi> > Q; Q.push(make_pair(0,0)); while(not Q.empty()){ double cost = Q.top().first; int where = Q.top().second; Q.pop(); if(used[where]) continue; ret += cost; used[where] = true; for(int i=0;i<n;i++){ Q.push(make_pair(D[where][i],i)); } } cout << ret << endl; } return 0; }
これの実行時間は、250MSで、そこそこっぽい。
http://d.hatena.ne.jp/mickey24/20090605/1244132474