UVa 539 - The Settlers of Catan, 简单回溯

2023-10-30 11:40

本文主要是介绍UVa 539 - The Settlers of Catan, 简单回溯,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

FILE539 - The Settlers of Catan3761
54.91%
1773
93.06%

题目链接:

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=108&page=show_problem&problem=480


题目类型: 回溯法


原题:

Within Settlers of Catan, the 1995 German game of the year, players attempt to dominate an island by building roads, settlements and cities across its uncharted wilderness.

You are employed by a software company that just has decided to develop a computer version of this game, and you are chosen to implement one of the game's special rules:


When the game ends, the player who built the longest road gains two extra victory points.


The problem here is that the players usually build complex road networks and not just one linear path. Therefore, determining the longest road is not trivial (although human players usually see it immediately).


Compared to the original game, we will solve a simplified problem here: You are given a set of nodes (cities) and a set of edges (road segments) of length 1 connecting the nodes. The longest road is defined as the longest path within the network that doesn't use an edge twice. Nodes may be visited more than once, though.


Example: The following network contains a road of length 12.

o        o -- o        o\      /      \      /o -- o        o -- o/      \      /      \
o        o -- o        o -- o\      /o -- o

样例输入:

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

题目大意:

输入一张无向图, 然后要求输出这张图最长的一条路径。 点可以重复走,但是边不能重复走。


思路与总结:

很简单的一道回溯递归题, 直接枚举所有点,然后从这个点开始递归搜索,记录路径数量,最后更新维护一个最大值。


代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#define MAXN 30
using namespace std;
int n,m, G[MAXN][MAXN], vis[MAXN][MAXN], maxNum;void dfs(int u, int num){for(int v=0; v<n; ++v){if(G[u][v] && !vis[u][v]){vis[u][v] = vis[v][u] = 1;dfs(v, num+1);vis[u][v] = vis[v][u] = 0;}}if(num > maxNum) maxNum = num;
}int main(){
#ifdef LOCALfreopen("input.txt","r",stdin);
#endifint a,b;while(~scanf("%d %d", &n, &m)){if(!n && !m) break;memset(G, 0, sizeof(G));for(int i=0; i<m; ++i){scanf("%d %d", &a, &b);++G[a][b];  ++G[b][a];}maxNum = -2147483645;for(int i=0; i<n; ++i){memset(vis, 0, sizeof(vis));dfs(i, 0);}printf("%d\n",maxNum);} return 0;
}


——  生命的意义,在于赋予它意义。

 


          原创  http://blog.csdn.net/shuangde800  , By   D_Double  (转载请标明)





这篇关于UVa 539 - The Settlers of Catan, 简单回溯的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/307670

相关文章

Mysql表的简单操作(基本技能)

《Mysql表的简单操作(基本技能)》在数据库中,表的操作主要包括表的创建、查看、修改、删除等,了解如何操作这些表是数据库管理和开发的基本技能,本文给大家介绍Mysql表的简单操作,感兴趣的朋友一起看... 目录3.1 创建表 3.2 查看表结构3.3 修改表3.4 实践案例:修改表在数据库中,表的操作主要

springboot简单集成Security配置的教程

《springboot简单集成Security配置的教程》:本文主要介绍springboot简单集成Security配置的教程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录集成Security安全框架引入依赖编写配置类WebSecurityConfig(自定义资源权限规则

如何使用Python实现一个简单的window任务管理器

《如何使用Python实现一个简单的window任务管理器》这篇文章主要为大家详细介绍了如何使用Python实现一个简单的window任务管理器,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起... 任务管理器效果图完整代码import tkinter as tkfrom tkinter i

C++中函数模板与类模板的简单使用及区别介绍

《C++中函数模板与类模板的简单使用及区别介绍》这篇文章介绍了C++中的模板机制,包括函数模板和类模板的概念、语法和实际应用,函数模板通过类型参数实现泛型操作,而类模板允许创建可处理多种数据类型的类,... 目录一、函数模板定义语法真实示例二、类模板三、关键区别四、注意事项 ‌在C++中,模板是实现泛型编程

使用EasyExcel实现简单的Excel表格解析操作

《使用EasyExcel实现简单的Excel表格解析操作》:本文主要介绍如何使用EasyExcel完成简单的表格解析操作,同时实现了大量数据情况下数据的分次批量入库,并记录每条数据入库的状态,感兴... 目录前言固定模板及表数据格式的解析实现Excel模板内容对应的实体类实现AnalysisEventLis

Java中数组转换为列表的两种实现方式(超简单)

《Java中数组转换为列表的两种实现方式(超简单)》本文介绍了在Java中将数组转换为列表的两种常见方法使用Arrays.asList和Java8的StreamAPI,Arrays.asList方法简... 目录1. 使用Java Collections框架(Arrays.asList)1.1 示例代码1.

Java8需要知道的4个函数式接口简单教程

《Java8需要知道的4个函数式接口简单教程》:本文主要介绍Java8中引入的函数式接口,包括Consumer、Supplier、Predicate和Function,以及它们的用法和特点,文中... 目录什么是函数是接口?Consumer接口定义核心特点注意事项常见用法1.基本用法2.结合andThen链

C++初始化数组的几种常见方法(简单易懂)

《C++初始化数组的几种常见方法(简单易懂)》本文介绍了C++中数组的初始化方法,包括一维数组和二维数组的初始化,以及用new动态初始化数组,在C++11及以上版本中,还提供了使用std::array... 目录1、初始化一维数组1.1、使用列表初始化(推荐方式)1.2、初始化部分列表1.3、使用std::

redis群集简单部署过程

《redis群集简单部署过程》文章介绍了Redis,一个高性能的键值存储系统,其支持多种数据结构和命令,它还讨论了Redis的服务器端架构、数据存储和获取、协议和命令、高可用性方案、缓存机制以及监控和... 目录Redis介绍1. 基本概念2. 服务器端3. 存储和获取数据4. 协议和命令5. 高可用性6.

JAVA调用Deepseek的api完成基本对话简单代码示例

《JAVA调用Deepseek的api完成基本对话简单代码示例》:本文主要介绍JAVA调用Deepseek的api完成基本对话的相关资料,文中详细讲解了如何获取DeepSeekAPI密钥、添加H... 获取API密钥首先,从DeepSeek平台获取API密钥,用于身份验证。添加HTTP客户端依赖使用Jav