UVa 539 The Settlers of Catan

题目描述

题目要求在一个无向图中找出最长路径（边不重复，节点可重复）。图中节点的度数不超过333，节点数n≤25n \le 25n≤25，边数m≤25m \le 25m≤25。输出最长路径的边数（即路径长度）。

输入格式

输入包含多个测试用例。每个测试用例的第一行包含两个整数nnn和mmm（2≤n≤252 \le n \le 252≤n≤25，1≤m≤251 \le m \le 251≤m≤25）。接下来mmm行，每行两个整数uuu和vvv，表示一条无向边。输入以0 0结束。

输出格式

对于每个测试用例，输出一行一个整数，表示最长路径的边数。

样例

输入

3 2 0 1 1 2 15 16 0 2 1 2 2 3 3 4 3 5 4 6 5 7 6 8 7 8 7 9 8 10 9 11 10 12 11 12 10 13 12 14 0 0

输出

2 12

题目分析

本题的核心是在无向图中搜索最长路径（边不可重复，节点可重复）。由于m≤25m \le 25m≤25，可以直接使用深度优先搜索（DFS\texttt{DFS}DFS）枚举所有路径。

搜索策略

• 从每个节点出发，进行DFS\texttt{DFS}DFS，记录当前路径长度。
• 使用visited[u][v]\textit{visited}[u][v]visited[u][v]标记边是否已被使用（无向边双向标记）。
• 每当到达一个节点，更新最大长度。
• 递归搜索所有相邻的未使用边。

剪枝

由于度数≤3\le 3≤3，搜索分支有限，无需额外剪枝。

复杂度分析

最坏情况下，完全图K25K_{25}K25​的边数为300300300，但本题m≤25m \le 25m≤25，且度数≤3\le 3≤3，搜索空间有限。

代码实现

// The Settlers of Catan// UVa ID: 539// Verdict: Accepted// Submission Date:// UVa Run Time: s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constintMAX_V=30;intn,m,maxLength=0,visited[MAX_V][MAX_V],connected[MAX_V][MAX_V];voiddfs(intu,intlength){maxLength=max(maxLength,length);for(intv=0;v<n;v++)if(connected[u][v]&&!visited[u][v]&&!visited[v][u]){visited[u][v]=visited[v][u]=1;dfs(v,length+1);visited[u][v]=visited[v][u]=0;}}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intfrom,to;while(cin>>n>>m,n>0){memset(connected,0,sizeof(connected));for(inti=1;i<=m;i++){cin>>from>>to;connected[from][to]=connected[to][from]=1;}maxLength=0;for(inti=0;i<n;i++){memset(visited,0,sizeof(visited));dfs(i,0);}cout<<maxLength<<'\n';}return0;}