小游戏

红太狼 2022-05-28 07:10 167阅读 0赞

## 问题描述 ##

小李很喜欢玩计算机游戏，特别是战略游戏，但是有时他不能尽快找到解所以常常感到很沮丧。现在面临如下问题：他必须在一个中世纪的城堡里设防，城堡里的道路形成一棵无向树。要在结点上安排最少的士兵使得他们可以看到所有边。你能帮助他吗？

你的任务是给出士兵的最少数目。

## 输入格式 ##

输入包含多组数据。每组数据表示一棵树，在每组数据中：

第一行是结点的数目。

接下来的几行，每行按如下格式描述一个结点：

结点标识符 : ( 道路的数目 ) 结点标识符1 结点标识符2 …… 结点标识符道路的数目

或者

结点标识符 : (0)

对于 n (0<n<=1500) 个结点，结点标识符是一个从 0 到 n - 1 的整数。每条边在测试用例中只出现一次。

## 输出格式 ##

对于每组数据，各给出一个整数表示士兵的最少数目.

<table style="color:rgb(68,68,68);font-size:13px;line-height:25px;max-width:100%;border-spacing:0px;width:1650px;margin-bottom:20px;background-color:transparent;"> 
 <thead> 
  <tr> 
   <th style="padding:4px;line-height:20px;vertical-align:bottom;border-top-width:0px;">&nbsp;</th> 
   <th style="padding:4px;line-height:20px;vertical-align:bottom;border-top-width:0px;">测试输入<span><a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=input&amp;lang=zh_cn" title="关于“测试输入”的帮助" style="color:rgb(67,142,185);" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“测试输入”的帮助" style="vertical-align:text-bottom;border:0px;height:16px;padding-left:3px;width:16px;"></a></span></th> 
   <th style="padding:4px;line-height:20px;vertical-align:bottom;border-top-width:0px;">期待的输出<span><a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=expectedoutput&amp;lang=zh_cn" title="关于“期待的输出”的帮助" style="color:rgb(67,142,185);" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“期待的输出”的帮助" style="vertical-align:text-bottom;border:0px;height:16px;padding-left:3px;width:16px;"></a></span></th> 
   <th style="padding:4px;line-height:20px;vertical-align:bottom;border-top-width:0px;">时间限制<span><a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=timelimit&amp;lang=zh_cn" title="关于“时间限制”的帮助" style="color:rgb(67,142,185);" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“时间限制”的帮助" style="vertical-align:text-bottom;border:0px;height:16px;padding-left:3px;width:16px;"></a></span></th> 
   <th style="padding:4px;line-height:20px;vertical-align:bottom;border-top-width:0px;">内存限制<span><a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=memlimit&amp;lang=zh_cn" title="关于“内存限制”的帮助" style="color:rgb(67,142,185);" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“内存限制”的帮助" style="vertical-align:text-bottom;border:0px;height:16px;padding-left:3px;width:16px;"></a></span></th> 
   <th style="padding:4px;line-height:20px;vertical-align:bottom;border-top-width:0px;">额外进程<span><a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=nproc&amp;lang=zh_cn" title="关于“{$a} 个额外进程”的帮助" style="color:rgb(67,142,185);" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“{$a} 个额外进程”的帮助" style="vertical-align:text-bottom;border:0px;height:16px;padding-left:3px;width:16px;"></a></span></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td style="padding:4px;line-height:20px;vertical-align:middle;background-color:rgb(249,249,249);">测试用例 1</td> 
   <td style="padding:4px;line-height:20px;vertical-align:middle;background-color:rgb(249,249,249);"><a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=71143&amp;test=90953&amp;type=in&amp;download=0" style="color:rgb(67,142,185);font-size:9pt;" rel="nofollow">以文本方式显示</a> 
    <div style="vertical-align:top;padding:0px 5px 0px 0px;width:10em;height:10em;"> 
     <ol style="margin-bottom:0px;margin-left:2.5em;"> 
      <li style="font-family:Consolas, 'Courier New', Courier, mono, serif;margin:0px;padding:0px;"><span style="margin:0px;padding:0px;white-space:nowrap;background-color:rgb(211,211,211);">4↵</span></li> 
      <li style="font-family:Consolas, 'Courier New', Courier, mono, serif;margin:0px;padding:0px;"><span style="margin:0px;padding:0px;white-space:nowrap;background-color:rgb(211,211,211);">0:(1)&nbsp;1↵</span></li> 
      <li style="font-family:Consolas, 'Courier New', Courier, mono, serif;margin:0px;padding:0px;"><span style="margin:0px;padding:0px;white-space:nowrap;background-color:rgb(211,211,211);">1:(2)&nbsp;2&nbsp;3↵</span></li> 
      <li style="font-family:Consolas, 'Courier New', Courier, mono, serif;margin:0px;padding:0px;"><span style="margin:0px;padding:0px;white-space:nowrap;background-color:rgb(211,211,211);">2:(0)↵</span></li> 
      <li style="font-family:Consolas, 'Courier New', Courier, mono, serif;margin:0px;padding:0px;"><span style="margin:0px;padding:0px;white-space:nowrap;background-color:rgb(211,211,211);">3:(0)↵</span></li> 
      <li style="font-family:Consolas, 'Courier New', Courier, mono, serif;margin:0px;padding:0px;"><span style="margin:0px;padding:0px;white-space:nowrap;background-color:rgb(211,211,211);">5↵</span></li> 
      <li style="font-family:Consolas, 'Courier New', Courier, mono, serif;margin:0px;padding:0px;"><span style="margin:0px;padding:0px;white-space:nowrap;background-color:rgb(211,211,211);">3:(3)&nbsp;1&nbsp;4&nbsp;2↵</span></li> 
      <li style="font-family:Consolas, 'Courier New', Courier, mono, serif;margin:0px;padding:0px;"><span style="margin:0px;padding:0px;white-space:nowrap;background-color:rgb(211,211,211);">1:(1)&nbsp;0↵</span></li> 
      <li style="font-family:Consolas, 'Courier New', Courier, mono, serif;margin:0px;padding:0px;"><span style="margin:0px;padding:0px;white-space:nowrap;background-color:rgb(211,211,211);">2:(0)↵</span></li> 
      <li style="font-family:Consolas, 'Courier New', Courier, mono, serif;margin:0px;padding:0px;"><span style="margin:0px;padding:0px;white-space:nowrap;background-color:rgb(211,211,211);">0:(0)↵</span></li> 
      <li style="font-family:Consolas, 'Courier New', Courier, mono, serif;margin:0px;padding:0px;"><span style="margin:0px;padding:0px;white-space:nowrap;background-color:rgb(211,211,211);">4:(0)↵</span></li> 
     </ol> 
    </div></td> 
   <td style="padding:4px;line-height:20px;vertical-align:middle;background-color:rgb(249,249,249);"><a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=71143&amp;test=90953&amp;type=out&amp;download=0" style="color:rgb(67,142,185);font-size:9pt;" rel="nofollow">以文本方式显示</a> 
    <div style="vertical-align:top;padding:0px 5px 0px 0px;width:10em;height:10em;"> 
     <ol style="margin-bottom:0px;margin-left:2.5em;"> 
      <li style="font-family:Consolas, 'Courier New', Courier, mono, serif;margin:0px;padding:0px;"><span style="margin:0px;padding:0px;white-space:nowrap;background-color:rgb(211,211,211);">1↵</span></li> 
      <li style="font-family:Consolas, 'Courier New', Courier, mono, serif;margin:0px;padding:0px;"><span style="margin:0px;padding:0px;white-space:nowrap;background-color:rgb(211,211,211);">2↵</span></li> 
     </ol> 
    </div></td> 
   <td style="padding:4px;line-height:20px;vertical-align:middle;background-color:rgb(249,249,249);">1秒</td> 
   <td style="padding:4px;line-height:20px;vertical-align:middle;background-color:rgb(249,249,249);">64M</td> 
   <td style="padding:4px;line-height:20px;vertical-align:middle;background-color:rgb(249,249,249);">0</td> 
  </tr> 
 </tbody> 
</table>

解法一：用邻接表存储图

/*
    优先删除全部孤立点，随后考虑度为1的结点（即树中的叶子结点），
    因为叶子结点必须要被覆盖，将其与父亲结点比较可知，将士兵放置在父亲结点可得到更优解。
    删除父亲结点和叶结点，继续寻找新的叶子结点，直到所有结点都被覆盖。
    */

#include <stdio.h>
    #include <string.h>
    
    int  pr[1503][1503];//邻接表,每行第0个元素代表这个节点输入完后连接了多少个节点，即从第1个元素开始就是这个节点连接的其他节点
    
    int main(){
    	//freopen("1.txt", "r", stdin);
    	int r[1501], n, i, j, k, point, num, p, count, m, flag;
    	while (scanf("%d", &n) != -1){
    
    		flag = 0;
    
    		if (n == 1){      //如果只有一个点，答案为1
    			printf("1\n");
    			continue;
    		}
    		else{
    
    			memset(pr, -1, sizeof(pr));
    			memset(r, 0, sizeof(r));
    			for (int i = 0; i < n; i++)
    				pr[i][0] = 0;
    			//输入
    			for (i = 0; i<n; i++)
    			{
    				scanf("%d:(%d)", &point, &num);
    				if (num != 0){//如果输入的num有非0的，即图中有边,flag=1
    					flag = 1;
    				}
    				for (j = 0; j<num; j++)
    				{
    					scanf("%d", &p);
    					pr[point][0]++;//point点连接的节点个数加1
    					pr[point][pr[point][0]] = p;//point点后面依次添加p点
    					pr[p][0]++;//p点连接的节点个数加1
    					pr[p][pr[p][0]] = point;//p点后面依次添加point点
    					r[p]++;//p点度数加1
    					r[point]++;//point点度数加1
    				}
    			}
    
    			if (flag == 0){//如果图中没边
    				printf("0\n");
    				continue;
    			}
    			else{
    				count = 0;
    				m = n;//m变量用来覆盖所有点
    				while (m>0)
    				{
    					for (j = 0; j<n; j++)
    					{
    						if (r[j] == 1)//寻找度数为1的点,进行操作
    						{
    							r[j]--;//该点度数减1
    							m--;//图中少了一个点
    							k = pr[j][1]; //度数为1的节点只连接着1个节点,所以该行取下标为1的元素就是该度数为1的点的一个父节点k
    							pr[j][1] = -1;//少了一个点的话该度数为1的点就没有点了，将它仅连着的k点设置为-1，代表无点连接j了
    							count++;//在这个父节点上设置一个士兵
    							r[k] = 0;//接下来要删除k的所有子节点,将k的度数设置为0
    							m--; //图中又少了个点
    							for (i = 1; i <= pr[k][0]; i++)//在k连接的点中找到j，并将这个j的位置设置为-1,k和j就彻底断绝了关系,哈哈哈哈哈。！！！（打感叹号的代码是不是可以重构呢？）
    							{
    								if (pr[k][i] == j)
    								{
    									pr[k][i] = -1;
    									break;
    								}
    							}
    							//开始删除k的子节点
    							for (i = 1; i <= pr[k][0]; i++)
    							{
    								if (pr[k][i] == -1)continue;//如果当前位置的子节点已经删除过就不进行后面的操作
    								int mark = pr[k][i];//获得当前这个点的编号
    								
    								if (r[mark] == 1)//如果这个子节点是1度的
    								{
    									r[mark] = 0;
    									m--;//图中少了一个点
    									pr[k][i] = -1;//这干什么应该知道了吧
    									pr[mark][1] = -1;
    								}
    								else//如果这个子节点不是1度的
    								{
    									r[mark]--;
    									pr[k][i] = -1;
    									for (int i = 1; i <= pr[mark][0]; i++)//在mark连接的节点中找到k,将k的位置设为-1,mark和k又断绝了关系！！！（打感叹号的代码是不是可以重构呢？）
    									{
    										if (pr[mark][i] == k)
    										{
    											pr[mark][i] = -1;
    											break;
    										}
    									}
    								}
    							}
    						}
    					}
    				}
    
    				printf("%d\n", count);
    			}
    		}
    
    	}
    	return 0;
    }

![70][]

解法二：用邻接矩阵存储图

网上看了一个估计是学长写的吧，但是我不明白了，为什么邻接矩阵会比邻接表快？

解法一是我把他这个改成了邻接表的。

这下载的，花了我5金币

[https://download.csdn.net/download/jingmiaoxianren/2988552\#comment][https_download.csdn.net_download_jingmiaoxianren_2988552_comment]

/*
    优先删除全部孤立点，随后考虑度为1的结点（即树中的叶子结点），
    因为叶子结点必须要被覆盖，将其与父亲结点比较可知，将士兵放置在父亲结点可得到更优解。
    删除父亲结点和叶结点，继续寻找新的叶子结点，直到所有结点都被覆盖。
    */
    #include <stdio.h>
    #include <string.h>
    
    char pr[1501][1501];
    
    int main(){
    	//freopen("1.txt", "r", stdin);
    	int r[1501], n, i, j, k, t, point, num, p, count, m, flag;
    	while (scanf("%d", &n) != -1){
    
    		flag = 0;
    
    		if (n == 1){      //如果只有一个点，答案为1
    			printf("1\n");
    			continue;
    		}
    		else{
    
    			memset(pr, 0, sizeof(pr));
    			memset(r, 0, sizeof(r));
    
    			//输入
    			for (i = 0; i<n; i++)
    			{
    				scanf("%d:(%d)", &point, &num);
    				if (num != 0){//如果输入的num有非0的，即图中有边,flag=1
    					flag = 1;
    				}
    				r[point] += num;
    				for (j = 0; j<num; j++)
    				{
    					scanf("%d", &p);
    					pr[point][p] = pr[p][point] = 1;
    					r[p]++;
    				}
    			}
    
    			if (flag == 0){//如果图中没边
    				printf("0\n");
    				continue;
    			}
    			else{
    			count = 0;
    				m = n;//m变量用来覆盖所有点
    				while (m>0)
    				{
    					for (j = 0; j<n; j++)
    					{
    						if (r[j] == 1)//寻找度数为1的点,进行操作
    						{
    							r[j]--;
    							m--;
    							for (k = 0; k<n; k++)
    							{
    								if (pr[j][k] != 0)//找到该度数为为1的节点的一个父节点k
    								{
    									pr[j][k] = pr[k][j] = 0;
    									r[k] = 0;
    									count++;
    									m--;
    									break;
    								}
    							}
    							for (t = 0; t<n; t++)//找k的所有子节点
    							{
    								if (pr[k][t] == 1)
    								{
    									if (r[t] == 1)//如果这个子节点是1度的
    									{
    										pr[k][t] = pr[t][k] = 0;
    										m--;
    										r[t] = 0;
    									}
    									else{//如果这个子节点不是1度的
    										pr[k][t] = pr[t][k] = 0;
    										r[t]--;
    									}
    								}
    							}
    						}
    					}
    				}
    
    				printf("%d\n", count);
    			}
    		}
    
    	}
    	return 0;
    }

![70 1][]

[70]: /images/20220528/bb6db49879f144b9b9b5ed7189741e4e.png
[https_download.csdn.net_download_jingmiaoxianren_2988552_comment]: https://download.csdn.net/download/jingmiaoxianren/2988552#comment
[70 1]: /images/20220528/ccf2a2483de84692a13f6912e28a0ac4.png