第一行，一个整数N表示城市的数量（1<=N<=50）
接下来会有一个由‘Y’‘N’两个字符构成的N*N矩阵Link，表示城市的链接情况。
对于矩阵中某个元素Link[i][j]==‘Y‘表示城市i与城市j间有一条无向边，否则为‘N’表示没有边。
一行一个整数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; }
原文：http://www.cnblogs.com/ccz181078/p/5860819.html