点击打开链接
题目意思:给定n个节点,编号为0--n-1,在给定m条边,要求一条最长的路径
解题思路 回溯搜索每一点的最长的路径
代码:
//求解最长的路径长度,给个的是一个无向的图,那么我们可以用回溯法去做,只要去试探每一个点的最长的路径,然后得到最大的即可。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <list>
#include <vector>
#include <stack>
#include <cmath>
#include <algorithm>
#define eps 1e-8
using namespace std;
const int MAXN = 30;
int n, m, ans, tans;
int G[MAXN][MAXN];//存储地图
int vis[MAXN];//标记节点是否被走过
//搜索
int dfs(int pos , int max) {
if(max > tans)//更新临时的tans
tans = max;
for (int i = 0; i < n; i++) {
if (G[pos][i]) {
--G[pos][i];//无向图每一条边只能走一次
--G[i][pos];
vis[pos] = 1;//标记节点被走过
dfs(i , max+1);
++G[pos][i];//状态的回溯
++G[i][pos];
vis[pos] = 0;
}
}
return tans;//返回该点能走的最大值
}
void solve(){
int i , j;
int temp;
for(i = 0 ; i < n ; i++){
for(j = 0 ; j < n ; j++){
if(G[i][j]){//遍历每一个点
tans = 0;//初始化为0
temp = dfs(i , 0);
if(ans < temp)//更新最大的值
ans = temp;
}
}
}
}
//主函数
int main() {
int x, y;
while (scanf("%d%d%*c", &n, &m) && n && m) {
memset(G, 0, sizeof (G));
for (int i = 0; i < m; i++) {
scanf("%d%d", &x, &y);
G[x][y] = 1;//因为每一条边只能走一次,所以标记为1即可
G[y][x] = 1;
}
ans = 0;
solve();
printf("%d\n", ans);
}
return 0;
}
分享到:
相关推荐
colonizers, 在"The Settlers of Catan" Teuber的上 Colonizers 基于流行的棋盘游戏 "catan"( 以前是"catan的Settlers")的HTML5多人游戏,由克劳斯 Teuber 。工作在多个设备( 台式机,平板电脑和移动电话) 。 在本地...
JSettlers2是用Java编写的卡坦岛定居者棋盘游戏的基于Web的版本。 该客户端-服务器系统支持人和/或AI机器人之间的多个同时游戏。 最初由Robert S Thomas撰写,是AI论文... sourceforge CVS的历史可以追溯到2012-09-28。
数字催化基于棋盘游戏“ Catan Settlers of Catan”的数字游戏在查看项目。
在“ The Settlers Online”中使用您喜欢的地图,而无需在选项卡或应用程序之间切换。 TSOW是用于“ The Settlers Online”游戏的小部件。 它使您无需查看选项卡或应用程序即可查看自己的冒险地图。 此扩展名是游戏...
Catan的Java Settlers是经典棋盘游戏“ Catan的Settlers”的Java版本。 该游戏包括具有挑战性的计算机AI播放器,并支持多点触控输入,以在多点触控桌上进行游戏。
建设项目 去做
Catan纸牌接龙定居者是克劳斯·特伯(Klaus Teuber)流行的棋盘游戏“ The Cattlers of Catan”或“ Die Siedler Von Catan”的Java版本。 该项目使您可以与计算机AI玩棋盘游戏。
在“The Settlers Online”中使用您最喜爱的地图,而无需在选项卡或应用程序之间切换。 TSOW是用于“ The Settlers Online”游戏的小部件。 它使您无需查看选项卡或应用程序即可查看自己的冒险地图。 此扩展名是游戏...
More information can be found on the project's website at www.settlers-android-clone.com Warning: Alpha Status The game is currently in an alpha status! Therefore bugs, frequent changes making saved ...
当Catan板有焦点时,按住ALT_C,这将使OptionPane出现并允许取消。 至于我想谈论的游戏新增内容,我为游戏实现了一个类别系统,这使其难度更大(它是可选的;如果您要使用标准游戏,请选择定居者类别)以及可能影响...
吉打定居者关于K'tah的定居者是一款回合制多人视频棋盘游戏,灵感来自Catan的Settlers和K'tah的游戏系列! 这是LMU计算机科学和动画部门之间的共同努力,其开发团队由四个LMU班级的2021名学生组成。 K'tah的定居者以...
对出色的经典回合制棋盘游戏 Settlers of Catan 的现代改编,玩家竞相收集资源和胜利点以赢得比赛。 Github 工作流程 Master 随时准备部署到 Heroku 功能分支上的功能 由队友审查的拉取请求 团队动力 敏捷 在需要时...
该项目最初是The Settlers II.net地图生成器,但随着时间的推移,它将得到更好的抽象,以便地图生成器部分成为独立模块,也可用于其他游戏和项目。 该项目的当前状态在上运行 您可以在各自的站点上阅读有关更多信息...
殖民者 ... 适用于多种设备(台式机、平板电脑和手机)。 从分叉。 一项正在进行的工作! 《殖民者》正在开发中,还有几个关键的游戏功能有待实现。 预计会发生重大变化,并且数据库架构可能会发生变化。...
Settlers IV脚本编辑器 启动S4Editor.exe时启动的一个小窗口。 将旧的MapGenerator.dll重命名为MapGenerator2.dll,然后将此程序(也称为MapGenerator.dll)拖到S4 / Editor /文件夹中,然后关闭。
《定居者II》文档 随着时间的流逝,本文档可以有望解释游戏使用的文件格式中的每个字节。 在撰写本文时,我们知道创建完美的WLD / SWD映射所需的一切。 也可以替换原始游戏中的现有图形,尽管仍然没有开源工具可以...
定居者 本项目拟对Blue Byte 1998年出版的著名策略游戏《定居者3》进行翻拍。该项目采用Java开发,运行于PC(Windows/Linux)、Mac和Android上。 更多信息可以在项目网站 警告:Alpha 状态 该游戏目前处于alpha状态...
适用于MIDP 1.0移动设备的Catan Settlers版本,带有彩色界面。
小指 Web扩展使收藏品易于查找! 什么? 小指取代 与 怎么样? 它将重定向浏览器发出的某些请求(请参阅 )。 有关详细信息,请查看 。 哪里? 一键即可安装Pinky。 用法 ...如果你真的喜欢...
Catan经典的Settlers的另一个版本,旨在在Windows,Linux和OSX上播放,并支持所有正式的扩展以及一些非官方的扩展。 支持多人网络播放。