【洛谷】P1294 高手去散步

• 2021 年 4 月 11 日
• 筆記
• DFS, 洛谷, 遞歸

題目背景

高手最近談戀愛了。不過是單相思。「即使是單相思，也是完整的愛情」，高手從未放棄對它的追求。今天，這個陽光明媚的早晨，太陽從西邊緩緩升起。於是它找到高手，希望在晨讀開始之前和高手一起在鰲頭山上一起散步。高手當然不會放棄這次夢寐以求的機會，他已經準備好了一切。

題目描述

鰲頭山上有n個觀景點，觀景點兩兩之間有游步道共m條。高手的那個它，不喜歡太刺激的過程，因此那些沒有路的觀景點高手是不會選擇去的。另外，她也不喜歡去同一個觀景點一次以上。而高手想讓他們在一起的路程最長（觀景時它不會理高手），已知高手的穿梭機可以讓他們在任意一個觀景點出發，也在任意一個觀景點結束。

輸入格式

第一行，兩個用空格隔開的整數n、m. 之後m行，為每條游步道的資訊：兩端觀景點編號、長度。

輸出格式

一個整數，表示他們最長相伴的路程。
輸入輸出樣例
輸入#1
4 6
1 2 10
2 3 20
3 4 30
4 1 40
1 3 50
2 4 60

輸出#1
150

說明/提示
對於100%的數據:n≤20，m≤50，保證觀景點兩兩之間不會有多條游步道連接.

解釋都在程式碼注釋中

#include<bits/stdc++.h>
using namespace std;

const int M = 50 + 10;
int n, m;
int maxmetre, sum;						//最大長度和目前長度 
int road[M][M];							 
bool vis[M];							//標記數組 

void dfs(int x)							
{
	for(int j = 1; j <= n; j++)			 //逐列判斷 
	{
		if(road[x][j] && vis[j] == 0)	 //若當前路徑存在且要到達的點未曾走過 
		{
			sum += road[x][j];				
			vis[j] = 1;					 //把到達的點標記 
			dfs(j);						 //以到達的點為基點開始遞歸 
			sum -= road[x][j];			 //回溯 
		}
	}		
	maxmetre = max(sum, maxmetre);		 //找出最長路徑 
	vis[x] = 0;							 //回溯 
	return;
}

int main()
{
	cin >> n >> m;
	for(int i = 1; i <= m; i++)
	{
		int n1, n2, metre;				//metre是道路之間的長度 
		cin >> n1 >> n2 >> metre;
		road[n1][n2] = metre;			//注意是無向圖 
		road[n2][n1] = metre;
	}
	
	for(int i = 1; i <= n; i++)			//遍歷，嘗試從不同的點作為起點開始搜索 
	{
		vis[i] = 1;						//將該點標記 
		dfs(i);							//i作為 "行"， 開始搜索 
		memset(vis, 0, sizeof(vis));	//回溯，這個點作為起點搜索結束後，將標記數組情況，方便下一個點作為起點搜索 
	}
	
	cout << maxmetre << endl;
	
	return 0;
 }