鱼C论坛

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

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

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

马上注册加入鱼C,享用更多服务吧^_^

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

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
最佳答案
0 
 楼主| 发表于 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
最佳答案
0 
 楼主| 发表于 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
最佳答案
0 
 楼主| 发表于 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
*滑块验证:
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关闭

小甲鱼强烈推荐上一条 /1 下一条

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号 )

GMT+8, 2018-7-21 23:37

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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