TopCoder SRM 503 Div2 Hard KingdomXCitiesandVillagesAnother

Div2 Hardとはいえ簡単めな問題。
http://community.topcoder.com/stat?c=problem_statement&pm=10835

問題

N個の町とM個の村があり、それぞれの座標が与えられる。

各村が、町とつながるか町とつながっている村とつながるよう道路を整備したい。
道路の整備コストはユークリッド距離と一致する。
また、道路を整備する順番は任意である。

条件を満たす最小総整備コストを答えよ。

解法

町同士はすでに接続されていると考えたうえで最小部分木問題を解けばよい。
以下はクラスカル法を適当にO(M^2*(N+M))で実装したもの。
N,M<=50なので時間は余裕。

double dist[100][100];
class KingdomXCitiesandVillagesAnother {
	public:
	double determineLength(vector <int> cityX, vector <int> cityY, vector <int> villageX, vector <int> villageY) {
		int N=cityX.size();
		int M=villageX.size();
		int con[51],i,j;
		double tot=0;
		ZERO(con);
		
		FOR(i,M) {
			FOR(j,N) dist[i][j]=sqrt((cityX[j]-villageX[i])*(ll)(cityX[j]-villageX[i]) + (cityY[j]-villageY[i])*(ll)(cityY[j]-villageY[i]));
			FOR(j,M) dist[i][N+j]=sqrt((villageX[j]-villageX[i])*(ll)(villageX[j]-villageX[i]) + (villageY[j]-villageY[i])*(ll)(villageY[j]-villageY[i]));
		}
		
		FOR(i,M) {
			int id=-1;
			double mi=1e20;
			FOR(i,M) if(con[i]==0) {
				FOR(j,N) if(dist[i][j]<mi) mi=dist[i][j],id=i;
				FOR(j,M) if(dist[i][N+j]<mi && con[j]) mi=dist[i][N+j],id=i;
			}
			
			tot+=mi;
			con[id]=1;
		}
		
		return tot;
	}
}

まとめ

これ1000ptよりは小さかったかもな。