某车企笔试题解答（2）

目录

承接前面的问题，附加题：

答：

1修改对DAG进行拓扑排序的函数

2 求解

以下是代码清单：

运行结果：

3 时间复杂度分析

---

承接前面的问题，附加题：

如果棋盘非常大（0

答：

本问题虽然沿用前一个问题的数学模型DAG，但是应充分利用只有很少的格子上有豆子的条件，在计算中尽量排除那些没有豆子的格子，才能降低时间复杂度。

将棋盘上有豆子的格点两两连起来，忽略没有豆子的格点，组成一个有向无环图(DAG)。连接任意两点之间的边的指向同样要保证是从左向右，从上到下。无法满足此要求的两点不连接。由于每个格子只有一个豆子，所以这个DAG的每条边的权重都是相等的，不妨设为1。要让吃豆人吃到最多的豆子，就变成了搜索此DAG的最长路径的问题。

解答分为3部分：一、修改对DAG进行拓扑排序的函数，在保证排序正确性的基础上降低其复杂度；二、求解；三、时间复杂度分析。

1修改对DAG进行拓扑排序的函数

在拓扑排序中，从顶点u到顶点v的每个有向边uv，u在排序中都在v之前。这里我们重写上题解答中的拓扑排序函数topologicalSortUtil()。新函数不再对棋盘上每一个格子进行排序，而是只对含有豆子的格子进行拓扑排序。

排序步骤如下：

1) 找到一个含有豆子的格子u，其坐标为(x,y)，同时建立一个变量，记录以u为起点的边数。

2) 找到另外一个有豆子的格子v，其坐标为(s,t)。

3) 假如s>=x 且 t>=y，则u可以到达v，于是以u为起点的边数加1，并在两者之间建立一条边，从u指向v；否则则不加1。

4) 重复2)和3)的操作，遍历所有的k-1个格子，算出以u为起点的边总数。

5) 重复1)2)3)4)的操作，遍历所有的k个格子，算出每个有豆子的格子的边数。

6) 准备一个stack，存放拓扑排序后的顶点集合。

7) 找到所有的以其自身为起点的边总数为0的格子，将它们放入stack。既然不存在以它们为起点的边，那么这些格子之间不会有边连接。根据拓扑排序的性质，“从顶点u到顶点v的每个有向边uv，u在排序中都在v之前”,这些格子不论在stack中彼此次序如何，都不会违背这个性质。

8) 找到所有的以其自身为起点的边总数为1的格子，将它们放入stack。这些格子彼此之间不会相互连接。(假如这些格子彼此之间存在边连接，那么作为这条边起点的格子的边总数将至少等于2—这条边的终点的格子算一个，而既然这条边的终点的格子的边总数为1，以其为起点的边指向的格子又算一个—也就破坏了“边总数为1的”的假设。)由于相互不连接，它们相互的次序不会破坏拓扑排序的性质。

9) 找到所有的以其自身为起点的边总数为p(p=2,3,4,….)的格子，将它们放入stack。这些格子彼此之间不会相互连接。由于相互不连接，它们相互的次序不会破坏拓扑排序的性质。

10) 重复第9步，直到所有的含有豆子的格子全被录入stack。

11) 将格子(0,0)作为最顶层的元素放入stack。拓扑排序完成。

2 求解

1) 输入变量是一个vector，vector由所有含有豆子的格子组成。每个格子用一个二元结构体表示。结构体的两个分量分别表示格子的横坐标和纵坐标。

2) 按照前面的步骤对这个vector进行拓扑排序。排序的同时也生成了相应的DAG。

3) 调用前一个问题中的函数Graph::longestPath(int s)返回最长路径。

以下是代码清单：

// A C++ program to find single source longest distances
 
// in a DAG
 
#include 
 
#include 
 
#include 
 
#include 
 
#include 
 
#include 
 
#define NINF INT_MIN
 
using namespace std;
 
 
 
 
 
struct ST_POS
 
{
 
    int     x;
 
    int     y;
 
};
 
// Graph is represented using adjacency list. Every
 
// node of adjacency list contains vertex number of
 
// the vertex to which edge connects. It also
 
// contains weight of the edge
 
class AdjListNode {
 
    int v;
 
    int weight;
 
 
 
public:
 
    AdjListNode(int _v, int _w)
 
    {
 
        v = _v;
 
        weight = _w;
 
    }
 
    int getV() { return v; }
 
    int getWeight() { return weight; }
 
};
 
 
 
// Class to represent a graph using adjacency list
 
// representation
 
class Graph {
 
    int V; // No. of vertices'
 
 
 
    // Pointer to an array containing adjacency lists
 
    list* adj;
 
    list<int>        *   pPath;
 
    unique_ptr<int[]>    m_upCount;
 
 
 
public:
 
    Graph(int V); // Constructor
 
    ~Graph(); // Destructor
 
 
 
    // function to add an edge to graph
 
    void addEdge(int u, int v, int weight);
 
 
 
    // Finds longest distances from given source vertex
 
    void longestPath(int s, stack<int>);
 
    // A function used by longestPath
 
    stack<int> topologicalSortUtil(vector);
 
};
 
 
 
Graph::Graph(int V) // Constructor
 
{
 
    this->V = V;
 
    adj = new list[V];
 
    pPath = new list<int>[V];
 
    m_upCount.reset(new int[V]);
 
}
 
 
 
Graph::~Graph() // Destructor
 
{
 
    delete[] adj;
 
    delete[] pPath;
 
}
 
 
 
void Graph::addEdge(int u, int v, int weight)
 
{
 
    AdjListNode node(v, weight);
 
    adj[u].push_back(node); // Add v to u's list
 
}
 
 
 
//排序，并产生DAG
 
stack<int> Graph::topologicalSortUtil(vector vecPos)
 
{
 
    int iLen = vecPos.size();
 
    for (int k = 0; k < iLen; k++)
 
    {
 
        //找到一个含有豆子的格子u，其坐标为(x,y)，同时建立一个变量，记录以u为起点的边数
 
        int iCount = 0;
 
        ST_POS u = vecPos.at(k);
 
        for (int l = 0; l < iLen; l++)
 
        {
 
             if (l != k)
 
             {
 
                 ST_POS v = vecPos.at(l);
 
                 //找到另外一个有豆子的格子v，其坐标为(s,t)
 
                 if (v.x >= u.x && v.y >= u.y)
 
                 {
 
                     //假如s>=x 且 t>=y，则u可以到达v，于是以u为起点的边数加1，并在两者之间建立一条边，从u指向v；否则则不加1
 
                     iCount++;
 
                     addEdge(k, l, 1);//由于每个格子只有一个豆子，所以这个DAG的每条边的权重都是相等的，不妨设为1。
 
                 }
 
             }
 
        }
 
 
 
        m_upCount[k] = iCount;
 
    }
 
 
 
    //找到所有的以其自身为起点的、边总数为p(p=0,1,2,3,4,….)的格子，将它们放入stack，并且放在边总数为p-1的格子之前
 
    stack<int> Stack;
 
    int iLevel = 0;
 
    while (Stack.size() < iLen)
 
    {
 
        for (int k = 0; k < iLen; k++)
 
        {
 
             if (m_upCount[k] == iLevel)
 
                 Stack.push(k);
 
        }
 
        iLevel++;
 
    }
 
   
 
    return Stack;
 
}
 
 
 
// The function to find longest distances from a given vertex.
 
void Graph::longestPath(int s, stack<int> Stack)
 
{
 
    int * dist = new int[V];
 
    // Initialize distances to all vertices as infinite and
 
    // distance to source as 0
 
    for (int i = 0; i < V; i++)
 
    {
 
        pPath[s].clear();
 
        dist[i] = NINF;
 
    }
 
       
 
    dist[s] = 0;
 
    pPath[s].push_back(s);
 
 
 
    // Process vertices in topological order
 
    while (Stack.empty() == false) {
 
        // Get the next vertex from topological order
 
        int u = Stack.top();
 
        Stack.pop();
 
 
 
        // Update distances of all adjacent vertices
 
        list::iterator i;
 
        if (dist[u] != NINF) {
 
             for (i = adj[u].begin(); i != adj[u].end(); ++i)
 
             {
 
                 if (dist[i->getV()] < dist[u] + i->getWeight())
 
                 {
 
                     //更新与u相连的各个顶点到s的距离
 
                     dist[i->getV()] = dist[u] + i->getWeight();
 
                     //更新具体路径
 
                     pPath[i->getV()].assign(pPath[u].begin(), pPath[u].end());
 
                     pPath[i->getV()].push_back(i->getV());
 
                 }  
 
             }
 
        }
 
    }
 
    // Print the calculated longest distances
 
    for (int i = 0; i < V; i++)
 
    {
 
        cout << "length:                                      -----------";
 
        (dist[i] == NINF) ? cout << "unReachable" : cout << dist[i];
 
        cout<< endl;
 
        cout << "path: ";
 
        for (const auto & item : pPath[i])
 
        {
 
             cout << item << " ";
 
        }
 
        cout << endl;
 
    }
 
       
 
    delete [] dist;
 
}
 
 
 
// Driver program to test above functions
 
int main()
 
{
 
    vector vecNodes = { { 0, 0 }, { 0, 3 }, { 1, 2 }, { 1, 4 }, { 1, 5 }, { 1, 6 },
 
    { 2, 0 }, { 2, 1 }, { 2, 4 }, { 3, 3 }, { 3, 4 }, { 4, 4 }, { 5, 0 }, { 5, 2 }, { 5, 3 },
 
    { 6, 1 }, { 6, 3 }, { 6, 5 } };
 
 
 
    Graph g(vecNodes.size());
 
    stack<int> Stack = g.topologicalSortUtil(vecNodes);
 
 
 
    int s = 0;
 
    cout << "Following are longest distances from "
 
        "source vertex "
 
        << s << " \n";
 
    g.longestPath(s, Stack);
 
    cin.get();
 
 
 
    return 0;
 
}

运行结果：

最大路径长度是6，途径格子0-6-7-9-14-16-17

棋盘上豆子分布如图，数字是每个格子的编号：

3 时间复杂度分析

整个程序分为两部分：拓扑排序函数topologicalSortUtil和计算最长路径函数longestPath

1. 在拓扑排序的过程中遍历了所有的含有豆子的格子(k个)，并且对每个格子，又遍历了其他含有豆子的格子(k-1个)。因此拓扑排序的过程的时间复杂度为O(k2)。
2. longestPath函数遍历了DAG的所有顶点，也就是所有的含有豆子的格子，共k个。对于每个顶点，又更新了与之相连的所有其他顶点到(0,0)的距离，这些顶点的个数不超过k-1。所以longestPath函数带来的时间复杂度不超过O(k^2)。

综合1与2，整个程序的时间复杂度为O(k2" role="presentation">k2$k^2$)