題目

此題題目指定使用的演算法為

輸入輸出格式

此題測資會給定機場選址數量airportQ (n)、各機場建造成本cost (c)、任兩個機場間航線所創造的收益benefit (b)。

Sol.
先建立costArray, benefitArray, buildArray陣列，分別在陣列中存各機場建造成本、任兩個機場間航線所創造的收益、是否興建此機場（蓋 = 1, 不蓋 = 0 )。
宣告變數totalB，代表總利潤。

由於演算法設定我們先預設 n 個機場都要蓋，因此先宣告buildArray中各項皆為 0。

此題我所設的函數叫做tearDown，用來判斷在這一輪中是否有要拆的機場

設nowB為目前已加總的利潤、nowC為目前已加總的成本、MaxB為弱拆除其中一個機場所獲最大利潤、tear代表要拆除的機場，每跑進來一圈就要將tear初始化歸 0。

Pseudocode

tearDown：{
for i in range airportQ    // 若拆除第i個機場
    if 這個機場要蓋
		for j in range airportQ	// benefitArray[j][k] 的j
			if確定有要蓋第j個機場且j != i
				nowC += 第j個機場的成本
				for k in range airportQ
					if確定有要蓋第k個機場且k != i
						nowB += 第j個機場與第k個機場航線的利潤
			nowB -= nowC
			nowC 歸 0
// 這個else很重要，因為 nowB 一開始是 0，MaxB 一開始負很大，如果第 0 個機場不蓋那下面就會遇到bug
	else
		continue

if nowB比現在已知的最大利潤 MaxB 大 且 nowB 比跑進此函數進行下一輪前的總利潤 totalB 大
		MaxB = nowB
		tear = i

return tear	// 若不能再拆則回傳 -1
}

在main function中：
for i in range airportQ
	tear = tearDown(參數們)	// 呼叫函數
	if tear回傳的值不為 -1    // 代表有可以拆的機場，就會進行下一輪
		for j in range airportQ
			for k in range airportQ
				if i == tear或 k == tear		// 註1*
					totalB -= benefitArray[j][k]
					benefitArray[j][k] = 0	// 將與要拆掉的機場有關聯的航線利潤都歸0，註1
		totalB += cost[tear]	// 將要拆掉的機場成本加回來
		cost[tear] = 0	//將與要拆掉的機場之成本歸0，註1
		將buildArray[tear] 歸 0
	else
	break
最後輸出答案：buildArray;totalB

註1
此題因為機場拆掉之後即不會再讀取有關這個機場的資料，因此可以直接將costArray、benefitArray中的資料歸 0，但是這個方法比較取巧，若題目會再用到已拆除的機場的資料、或再判讀一次是否要興建此機場，則註1* if的條件還需再判斷j != k以及buildArray[j] == 1。