UVa 216

http://domen111.github.io/UVa-Easy-Viewer/?216

在平面座標上有 $n$ 個點，我們要用 $n-1$ 條網路線連接這 $n$ 個點

為了安裝方便，兩台電腦之間會多預留 $16$ 呎的網路線

是否能找到一種連接方式，使得電腦都有網路線連接，並且網路線總長度最少

$2 \leq n \leq 8$

想法

這一題的 $n$ 很小，所以我們可以考慮比較暴力的作法

任意選擇一個起點，然後往下任意選擇下一個點，一直做到每個點都選擇到了，然後計算長度，把當前最短的長度所經過的點都記錄下來

Code

//By Koios1143
#include<iostream>
#include<iomanip>
#include<cmath>
using namespace std;
int n, Case=1, x[10], y[10], tmpx[10], tmpy[10], rx[10], ry[10];
bool used[10];
double tot, min_dis;

// 計算兩點之間距離
double dist(int p, int q, int m, int n){
	return sqrt(pow(p-m, 2) + pow(q-n, 2));
}
// path 紀錄當前網路線總長度
void dfs(int depth, double path){
	if(depth == n){
		if(path < min_dis){
			min_dis = path;
			// 紀錄當前長度最短的路徑
			for(int i=0 ; i<n ; i++){
				rx[i] = tmpx[i];
				ry[i] = tmpy[i];
			}
		}
		return;
	}
	for(int i=0 ; i<n ; i++){
		if(!used[i]){
			used[i] = true;
			tmpx[depth] = x[i];
			tmpy[depth] = y[i];
			if(depth == 0) dfs(depth+1, 0);
			else dfs(depth+1, path+dist(tmpx[depth], tmpy[depth], tmpx[depth-1], tmpy[depth-1])+16);
			used[i] = false;
		}
	}
}

int main(){
	while(cin>>n && n){
		// 初始化最小值是一個極大值
		min_dis=2147483647;
		for(int i=0 ; i<n ; i++){
			cin>>x[i]>>y[i];
			used[i] = false;
		}
		dfs(0, 0);
		cout<<"**********************************************************\n";
		cout<<"Network #"<<Case++<<"\n";
		for(int i=1 ; i<n ; i++){
			cout<<"Cable requirement to connect ("<<rx[i-1]<<","<<ry[i-1]<<") to ("<<rx[i]<<","<<ry[i]<<") is "<<fixed<<setprecision(2)<<dist(rx[i-1], ry[i-1], rx[i], ry[i])+16<<" feet.\n";
		}
		cout<<"Number of feet of cable required is "<<min_dis<<".\n";
	}
	return 0;
}

時間複雜度分析

每筆測資輸入時間複雜度為 $O(n)$

DFS 每一層最多有 $n$ 種選擇，總共有 $n$ 層，並且最後一層需要 $O(n)$ 的時間複製當前答案

每筆測資 DFS 時間複雜度為 $O(n^n \times n) = O(n^{n+1})$

每筆測資總時間複雜度約為 $O(n^{n+2})$