输入
n m k
m个数，表示每层的节点个数
接下来m行是每层的节点，节点顺序是从左往右的
k个叶子节点
k*k个矩阵，表示叶子节点之间的距离
输出：
每个节点的父亲节点编号，root节点是0
题解：
1.很明显，相邻两个节点的距离如果是2，那么便是同一个父亲节点。
2.第一个点的父亲节点u，必定是上一层第一个非叶子节点fa
3.u左边的节点v
如果dis[u][v]==2，则fa[v]=fa[u]
否则，fa[v]为fa的下一个非叶子节点
所以很明显，dis矩阵得为n*n的大小，而不仅仅是k*k
4.由于一开始只知道各叶子节点之间的dis，所以从底层往上推。
每次求该层节点的父亲节点，同时更新上面一层的相邻节点的距离
一开始WA的原因是更新父节点的距离时，只更新了其到其它叶子节点的距离，没有更新到所有点的距离。。。
所以遇到下面的样例时候，dis[3][4]=-2，而不是2
1->2
2->3,2->4
3->5,3->6 4->7
5->8,5->9 6->10 7->11
11 5 4
1 1 2 3 4
1
2
3 4
5 6 7
8 9 10 11
8 9 10 11
0 2 4 6
2 0 4 6
4 4 0 6
6 6 6 0
错误的输出:0 1 2 0 3 3 4 5 5 6 7
正确的输出:0 1 2 2 3 3 4 5 5 6 7
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <string.h> using namespace std; const int maxn=105; int n,m,k; int depth[maxn]; //每层的节点个数 int layer[maxn][maxn]; //每层的节点 int fa[maxn]; //ans int leaves[maxn]; //叶子节点 int isleaves[maxn]; //是否为叶子节点 int dis[maxn][maxn]; int son[maxn]; //父亲节点的随便其中一个儿子就行，因为点u到fa的所有儿子的距离都一样 int main() { scanf("%d %d %d",&n,&m,&k); memset(isleaves,0,sizeof(isleaves)); memset(son,0,sizeof(son)); memset(dis,0,sizeof(dis)); for(int i=0;i<m;i++){ scanf("%d",&depth[i]); } for(int i=0;i<m;i++){ for(int j=0;j<depth[i];j++){ scanf("%d",&layer[i][j]); } } for(int i=0;i<k;i++){ scanf("%d",&leaves[i]); isleaves[leaves[i]]=1; } for(int i=0;i<k;i++){ for(int j=0;j<k;j++){ scanf("%d",&dis[leaves[i]][leaves[j]]); } } fa[layer[0][0]]=0; for(int i=0;i<depth[1];i++) fa[layer[1][i]]=layer[0][0]; for(int i=m-1;i>=2;i--){ int point=0;//i-1层中第一个不是叶子节点的节点，必定是当前节点的父亲 while(isleaves[layer[i-1][point]] && point<depth[i-1]){ point++; } int u=layer[i][0]; fa[u]=layer[i-1][point]; son[layer[i-1][point]]=u; //不能只更新父节点到其它叶子节点的距离，而是到其它所有点的距离 for(int kk=0;kk<n;kk++){ if(dis[u][kk]>0){ dis[fa[u]][kk]=dis[kk][fa[u]]=dis[u][kk]-1; } } for(int kk=0;kk<k;kk++){ dis[leaves[kk]][fa[u]]=dis[fa[u]][leaves[kk]]=dis[leaves[kk]][u]-1; } for(int j=1;j<depth[i];j++){ int v=layer[i][j]; //如果和上一个节点u距离为2，说明父亲节点是同一个 if(dis[u][v]==2){ fa[v]=fa[u]; } //否则，父亲节点是i-1层中下一个不是叶子节点的节点 else { point++; while(isleaves[layer[i-1][point]] && point<depth[i-1]){ point++; } fa[v]=layer[i-1][point]; son[layer[i-1][point]]=v; //更新父亲节点到其它节点的距离 for(int kk=0;kk<n;kk++){ if(dis[v][kk]>0){ dis[fa[v]][kk]=dis[kk][fa[v]]=dis[v][kk]-1; } } } u=v; } //更新i-1层相邻节点的距离 for(int kk=0;kk<depth[i-1]-1;kk++){ int na=layer[i-1][kk]; int nb=layer[i-1][kk+1]; int sona,sonb; /*只要有一方是叶子节点，那么dis已经有了 如果都不是，那么就是对应儿子节点之间的距离-1 因为是从底层往上推的，所以儿子所在那一层的相邻节点距离已经更新过了。 */ if(!isleaves[na] && !isleaves[nb]){ sona=son[na]; sonb=son[nb]; dis[na][nb]=dis[nb][na]=dis[sona][sonb]-2; } } } printf("%d",fa[1]); for(int i=2;i<=n;i++){ printf(" %d",fa[i]); } //printf(" "); return 0; }