首页 > 代码库 > 51nod 1314 定位系统
51nod 1314 定位系统
一个国家有N个城市（标号为0~N-1），这N个城市恰好由N-1条道路连接在一起（即N个城市正好构成一个树状结构）。这个国家的所有道路的长度都是1个长度单位。定义：两个城市间的距离是两个城市间的最短路的长度。
现在这个国家想建立一套定位系统，让国家的公民能通过这套系统定位自己所在的城市。该系统由K个有编号的信号站构成，不妨将它们标号为0，1,2,3，...,K-1。每个信号站会放在一个城市中，每个城市最多安放一个信号站，每个信号站将不停的向外界发送信。（值得注意的是，信号站i不一定要安放在城市i中，例如：信号站2可以放在城市3中，也可以放城市4中）对于一个公民来说，如果他在城市X，那么他打开手机定位时，手机将收集K个信号站的信号，并根据这些信息生成一个K个元素的数组Dis[]，其中Dis[i]记录着信号站i所在的城市与手机用户所在的城市（这里即为城市X）的距离。手机中的定位软件将根据该Dis[]数组来判断用户所在的城市编号。
由于信号站成本太高，该国家想尽可能少的购买信号站，那么问题来了,该国家最少需要安装多少个信号站才能唯一定位每一个城市？
友情提示：每个城市能被唯一定位的充要条件是，在每一个城市手机能接收到的数组Dis[]是互不相同的。
例如：这个国家有三个城市0,1,2，且链接关系为 0 -- 1 -- 2 （即0、1间有边，1、2间有边）。那么只需要一个基站就可以了。但是该基站需要放在城市0或城市2。如果放在城市0，那么：
在城市0：Dis = {0};
在城市1：Dis = {1};
在城市2：Dis = {2};
显然是可区分的。同理放在城市2中。
但是如果放在城市1中，三个城市的手机用户会得到如下数据：
在城市0：Dis = {1};
在城市1：Dis = {0};
在城市2：Dis = {1};
显然，城市0和城市2所获得的Dis[]数据相同，软件显然无法区分Dis={1}时，用户是在城市0呢？还是在城市2？所以该安放方法不是最佳的。
Input
第一行，一个整数N表示城市的数量（1<=N<=50）接下来会有一个由‘Y’‘N’两个字符构成的N*N矩阵Link，表示城市的链接情况。对于矩阵中某个元素Link[i][j]==‘Y‘表示城市i与城市j间有一条无向边，否则为‘N’表示没有边。Output
一行一个整数K，表示该城市最少需要多少个信号站才能实现每个城市的唯一定位。特判n=1时ans=0
成链时ans=1
其余情况，ans>0，枚举一个点作为其中一个信号站并作为根，可以发现存在一个最优解，信号站都在叶节点上，而对于非根非叶的点，它的所有链形子树（如果有，且链的一端连着这个点）可以有至多一棵没有信号站，其余每棵子树内都要有信号站，于是可以树形dp
#include<cstdio>int n;char s[53];int es[107],enx[107],e0[53],ep=2;int f[53],t[53];void dfs(int w,int pa){ f[w]=t[w]=0; int d=0; for(int i=e0[w];i;i=enx[i]){ int u=es[i]; if(u==pa)continue; if(!t[w])t[w]=1; else t[w]=2; dfs(u,w); f[w]+=f[u]; if(t[u]<=1)d=1; else if(t[u])t[w]=2; } if(t[w]==2)f[w]-=d; if(!t[w])f[w]=1;}int main(){ scanf("%d",&n); if(n==1)return puts("0"),0; for(int i=1;i<=n;++i){ scanf("%s",s+1); for(int j=1;j<=n;++j)if(s[j]==‘Y‘){ es[ep]=j;enx[ep]=e0[i];e0[i]=ep++; } } int ans=1000000; for(int i=1;i<=n;++i){ dfs(i,0); int v=f[i]+(t[i]==2); if(v<ans)ans=v; } printf("%d",ans); return 0;}
51nod 1314 定位系统
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。