鱼C论坛

 找回密码
 立即注册
查看: 2970|回复: 3

一道搜索回溯的题目求帮助,感谢!

[复制链接]
发表于 2018-5-15 21:01:16 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
题目描述 Description
一家电脑公司在N个城市卖笔记本电脑(3≤N≤35)。这些城市被标记成1,2,……N。这N个城市之间有M条直接相连的道路。现在电脑公司想在一些城市设立服务站点,使得对于任意一个城市,要么在这座城市有一个服务站,要么和这个城市直连的城市有一个服务站。 请写一个程序,计算在满足以上条件的情况下,这家公司最少需要建立多少个服务站。

输入描述 Input Description
输入最少包含1组关于城市信息的描述,最多包含10组关于城市信息的描述。每一组城市信息的描述以两个整数N和M开始,N和M以一个空格间开,N表示城市的个数,M表示这些城市之间的道路数。接下来M行,每行有两个以空格间开的整数,i j,表示第i个城市和第j个城市之间有道路相连。输入以两个以空格相间的0结束。

输出描述 Output Description
对于每一组城市的描述信息,计算出一个最少建立的服务站的个数并输出。

样例输入 Sample Input
8 12
1 2
1 6
1 8
2 3
2 6
3 4
3 5
4 5
4 7
5 6
6 7
6 8
0 0

样例输出 Sample Output
2
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2018-5-16 11:27:33 | 显示全部楼层

求助:
题目描述 Description
一家电脑公司在N个城市卖笔记本电脑(3≤N≤35)。这些城市被标记成1,2,……N。这N个城市之间有M条直接相连的道路。现在电脑公司想在一些城市设立服务站点,使得对于任意一个城市,要么在这座城市有一个服务站,要么和这个城市直连的城市有一个服务站。 请写一个程序,计算在满足以上条件的情况下,这家公司最少需要建立多少个服务站。

输入描述 Input Description
输入最少包含1组关于城市信息的描述,最多包含10组关于城市信息的描述。每一组城市信息的描述以两个整数N和M开始,N和M以一个空格间开,N表示城市的个数,M表示这些城市之间的道路数。接下来M行,每行有两个以空格间开的整数,i j,表示第i个城市和第j个城市之间有道路相连。输入以两个以空格相间的0结束。

输出描述 Output Description
对于每一组城市的描述信息,计算出一个最少建立的服务站的个数并输出。

样例输入 Sample Input
8 12
1 2
1 6
1 8
2 3
2 6
3 4
3 5
4 5
4 7
5 6
6 7
6 8
0 0

样例输出 Sample Output
2
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2018-5-16 18:58:58 | 显示全部楼层
题目描述 Description
一家电脑公司在N个城市卖笔记本电脑(3≤N≤35)。这些城市被标记成1,2,……N。这N个城市之间有M条直接相连的道路。现在电脑公司想在一些城市设立服务站点,使得对于任意一个城市,要么在这座城市有一个服务站,要么和这个城市直连的城市有一个服务站。 请写一个程序,计算在满足以上条件的情况下,这家公司最少需要建立多少个服务站。

输入描述 Input Description
输入最少包含1组关于城市信息的描述,最多包含10组关于城市信息的描述。每一组城市信息的描述以两个整数N和M开始,N和M以一个空格间开,N表示城市的个数,M表示这些城市之间的道路数。接下来M行,每行有两个以空格间开的整数,i j,表示第i个城市和第j个城市之间有道路相连。输入以两个以空格相间的0结束。

输出描述 Output Description
对于每一组城市的描述信息,计算出一个最少建立的服务站的个数并输出。

样例输入 Sample Input
8 12
1 2
1 6
1 8
2 3
2 6
3 4
3 5
4 5
4 7
5 6
6 7
6 8
0 0

样例输出 Sample Output
2
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2018-5-17 09:11:51 | 显示全部楼层

题目描述 Description
一家电脑公司在N个城市卖笔记本电脑(3≤N≤35)。这些城市被标记成1,2,……N。这N个城市之间有M条直接相连的道路。现在电脑公司想在一些城市设立服务站点,使得对于任意一个城市,要么在这座城市有一个服务站,要么和这个城市直连的城市有一个服务站。 请写一个程序,计算在满足以上条件的情况下,这家公司最少需要建立多少个服务站。

输入描述 Input Description
输入最少包含1组关于城市信息的描述,最多包含10组关于城市信息的描述。每一组城市信息的描述以两个整数N和M开始,N和M以一个空格间开,N表示城市的个数,M表示这些城市之间的道路数。接下来M行,每行有两个以空格间开的整数,i j,表示第i个城市和第j个城市之间有道路相连。输入以两个以空格相间的0结束。

输出描述 Output Description
对于每一组城市的描述信息,计算出一个最少建立的服务站的个数并输出。

样例输入 Sample Input
8 12
1 2
1 6
1 8
2 3
2 6
3 4
3 5
4 5
4 7
5 6
6 7
6 8
0 0

样例输出 Sample Output
2
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-28 19:18

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表