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$

数组来判断用户所在的城市编号。

由于信号站成本太高，该国家想尽可能少的购买信号站，那么问题来了,该国家最少需要安装多少个信号站才能唯一定位每一个城市？

友情提示：每个城市能被唯一定位的充要条件是，在每一个城市手机能接收到的数组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

4
NYYY
YNNN
YNNN
YNNN

j

题解：

　　这个题目首先就有非常多的结论，不发现根本动不了手。

　　1.我们可以发现，只要给两个点x和y装上了信号站，那么x到y，路径上的所有点都可以通过x，y唯一确定。这个是里面最显然的结论了吧。

　　2.上一条结论，我们可以进行推论，如果我们选择一个点为根，并把他装成信号站，那么显然，之后继续选择信号站选择叶子节点一定会比其他节点更优，因为路径更长，确定的更多。

　　3.对于一跳链的话，显然只需要一个点就可以控制全部。

　　4.对于一棵多差树，如果他有一棵子树，是链的话，那么只需要将其他子树的叶子标记，这个链就不必要了。（因为，其他子树都确定了，只有链不确定，那么链也就更着确定了）。

　　所以说，根据以上结论，我们就可以写一个dp，统计子树中所需要的站数，然后累加起来，叶子节点都需要一个站点，然后之后如果满足性质3，就要把答案-1，最后特判一下如果整个都是链的情况就可以了。

代码：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#define MAXN 1000
using namespace std;
int f[MAXN],t[MAXN];
char s[MAXN];
struct edge{
    int first;
    int next;
    int to;
}a[MAXN];
int n,num=0;

void addedge(int from,int to){
    a[++num].to=to;
    a[num].next=a[from].first;
    a[from].first=num;
}

void dfs(int now,int ff){
    f[now]=t[now]=0;
    int d=0;
    for(int i=a[now].first;i;i=a[i].next){
        int to=a[i].to;
        if(to==ff) continue;
        if(!t[now]) t[now]=1;
        else t[now]=2;
        dfs(to,now);
        f[now]+=f[to];
        if(t[to]<=1) d=1;
        else t[now]=2;
    }
    if(t[now]>=2) f[now]-=d;
    else if(!t[now]) f[now]=1;
}

int main()
{
    scanf("%d",&n);
    if(n==1){
        printf("0");
        return 0;
    }
    for(int i=1;i<=n;i++){
        scanf("%s",s+1);
        for(int j=1;j<=n;j++){
            if(s[j]=='Y') addedge(i,j);
        }
    }
    int ans=1<<30;
    for(int i=1;i<=n;i++){
        dfs(i,0);
        int hh=f[i]+(t[i]==2);
        ans=min(ans,hh);
    }
    printf("%d",ans);
    return 0;
}