微软2017笔试2

题目

代码

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N = 105;
int n, m, k;
int w[N][N];//距离矩阵
int deep[N];//每层节点数
int L[N];//叶子节点序号，从小到大，也是距离矩阵的表头
int vis[N];
int locfa[N];
int mp[N][N];//节点标号矩阵
int fa[N];//父亲节点
int fur[N], dfur[N];
bool Check(int x, int y)
{
    if (x == y)return true;
    return w[fur[x]][fur[y]] == 2 + dfur[x] + dfur[y];
}
void Solve()
{
    while (~scanf("%d%d%d", &n, &m, &k))
    {
        memset(w, -1, sizeof(w));
        memset(vis, 0, sizeof(vis));
        //存入每层节点数
        for (int i = 1; i <= m; i++)
            scanf("%d", deep + i);
        //读入每层节点标号
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= deep[i]; j++)
                scanf("%d", &mp[i][j]);
        for (int i = 1; i <= k; i++)
        {
            scanf("%d", L + i);
            fur[L[i]] = L[i];
            dfur[L[i]] = 0;
            vis[L[i]] = 1;
        }
        //存入距离矩阵
        for (int i = 1; i <= k; i++)
            for (int j = 1; j <= k; j++)
                scanf("%d", &w[L[i]][L[j]]);
        //每个节点的父亲设置为自己
        for (int i = 1; i<m; i++)
        {
            for (int j = 1; j <= deep[i]; j++)
                if (!vis[mp[i][j]])
                {
                    locfa[i] = j;
                    break;
                }
        }
        for (int i = m; i>1; i--)//i is now deep
        {
            int st = 1, j = 1;
            while (st <= deep[i])
            {
                while (j <= deep[i])
                {
                    if (Check(mp[i][st], mp[i][j]))
                    {
                        fa[mp[i][j]] = mp[i - 1][locfa[i - 1]];
                        j++;
                    }
                    else break;
                }
                fur[mp[i - 1][locfa[i - 1]]] = fur[mp[i][st]];
                dfur[mp[i - 1][locfa[i - 1]]] = dfur[mp[i][st]] + 1;
                st = j, locfa[i - 1]++;
                while (vis[mp[i - 1][locfa[i - 1]]] == 1)locfa[i - 1]++;
            }
        }
        for (int i = 1; i <= n; i++)
            printf("%d%c", fa[i], i == n ? '\n' : ' ');
    }
}
int main()
{
    freopen("in.txt", "r", stdin);
    Solve();
    return 0;
}

先记下来吧，大神的代码，没看太懂==