一個國家有N個城市（標號為0~N-1），這N個城市恰好由N-1條道路連接在一起（即N個城市正好構(gòu)成一個樹狀結(jié)構(gòu)）。這個國家的所有道路的長度都是1個長度單位。定義：兩個城市間的距離是兩個城市間的最短路的長度。
現(xiàn)在這個國家想建立一套定位系統(tǒng)，讓國家的公民能通過這套系統(tǒng)定位自己所在的城市。該系統(tǒng)由K個有編號的信號站構(gòu)成，不妨將它們標號為0，1,2,3，...,K-1。每個信號站會放在一個城市中，每個城市最多安放一個信號站，每個信號站將不停的向外界發(fā)送信。（值得注意的是，信號站i不一定要安放在城市i中，例如：信號站2可以放在城市3中，也可以放城市4中）對于一個公民來說，如果他在城市X，那么他打開手機定位時，手機將收集K個信號站的信號，并根據(jù)這些信息生成一個K個元素的數(shù)組Dis[]，其中Dis[i]記錄著信號站i所在的城市與手機用戶所在的城市（這里即為城市X）的距離。手機中的定位軟件將根據(jù)該Dis[]數(shù)組來判斷用戶所在的城市編號。
由于信號站成本太高，該國家想盡可能少的購買信號站，那么問題來了,該國家最少需要安裝多少個信號站才能唯一定位每一個城市？

友情提示：每個城市能被唯一定位的充要條件是，在每一個城市手機能接收到的數(shù)組Dis[]是互不相同的。

例如：這個國家有三個城市0,1,2，且鏈接關(guān)系為 0 -- 1 -- 2 （即0、1間有邊，1、2間有邊）。那么只需要一個基站就可以了。但是該基站需要放在城市0或城市2。如果放在城市0，那么：
在城市0：Dis = {0};
在城市1：Dis = {1};
在城市2：Dis = {2};
顯然是可區(qū)分的。同理放在城市2中。

但是如果放在城市1中，三個城市的手機用戶會得到如下數(shù)據(jù)：
在城市0：Dis = {1};
在城市1：Dis = {0};
在城市2：Dis = {1};
顯然，城市0和城市2所獲得的Dis[]數(shù)據(jù)相同，軟件顯然無法區(qū)分Dis={1}時，用戶是在城市0呢？還是在城市2？所以該安放方法不是最佳的。

解題報告:
用時：2h，4WA
這題比較簡單，首先要明白葉子節(jié)點必須選，因為一對葉子節(jié)點，除非在兩者之間建立基站，其他不管在它們的爸爸媽媽爺爺奶奶處建立都沒有辦法區(qū)分他們兩個，所以只有二選一，但是還有一個決策，記一個點的葉子節(jié)點數(shù)為\(cnt\)，那么如果這個點沒有父節(jié)點，顯然只需要建立\(cnt-1\)個即可，那么如果有父親節(jié)點，這個被獨立出來的葉子節(jié)點和他的父節(jié)點就無法區(qū)分，所以還需要決策，所以我們再枚舉一個根節(jié)點，并且強制根節(jié)點要選，那么剩余的這顆子樹就可和其區(qū)分開了，所以我們只需要保證每一個節(jié)點的子樹中，只有一個子樹沒有選即可，代碼簡短

#include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <cmath> #define RG register #define il inline #define iter iterator #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) using namespace std; const int N=55; int head[N],nxt[N<<1],to[N<<1],num=0,n,f[N],tot=0,du[N]; char s[N]; void link(int x,int y){nxt[++num]=head[x];to[num]=y;head[x]=num;} void dfs(int x,int last){int u,cnt=0;for(int i=head[x];i;i=nxt[i]){u=to[i];if(u==last)continue;dfs(u,x);if(du[u]==1 || !f[u])cnt++;f[x]+=f[u];}if(cnt>1)tot+=cnt-1,f[x]=cnt-1; } void work() {scanf("%d",&n);if(n==1){puts("0");return ;}int ans=N;for(int i=1;i<n;i++){scanf("%s",s+1);for(int j=i+1;j<=n;j++){if(s[j]=='Y')link(i,j),link(j,i),du[i]++,du[j]++;}}for(int i=1;i<=n;i++){memset(f,0,sizeof(f));tot=0;dfs(i,i);ans=Min(tot+1,ans);}printf("%d\n",ans); }int main() {work();return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/Yuzao/p/7598375.html

總結(jié)

以上是生活随笔為你收集整理的51Nod 1314 定位系统的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。