题解 P8893 「UOI-R1」智能推荐

刘辰雨 · 2022-12-10 23:01:09 · 题解

使用算法：拓扑排序

此题非常简单，是拓扑排序模板题，所以我打算讲一讲什么是拓扑排序，以及如何实现拓扑排序。

一、什么是拓扑排序？

对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边<u,v>∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。----百度百科。

看似非常难懂，但是我用人话解释给大家听，意思就是说：

对于一个节点为 [1,n] 的有向图，会有一些 [1,n] 的排列 ^*F，满足对于图中任意一条 i \rightarrow j (i,j \in [1,n]) 的边，j 在排列 ^*F 中的位置都在 i 的位置之后。这样的排列叫拓扑排列，求出这个排列的过程叫拓扑排序。

二、如何实现拓扑排序？

实现拓扑排序，说白了，就是求出一种拓扑排列。

为了方便解释，我们定义一条 i \rightarrow j 的边中，i 为 j 的前驱，j 为 i 的后继。每一个节点都可以有多个前驱和多个后继。

那么，不难发现，当我们构造拓扑序列时，考虑一个节点是否应该加入序列时，实际上应该考虑它的全部前驱是否已经在序列里，如果并非如此，那么就不能加入这个节点。

再次考虑一种情况，当我们已经把一个点加入序列后，对它的所有后继而言，它实际上已经失去了影响，换而言之，这个点还在不在已经没有关系了，所以我们可以直接“删去”这个点，将它与它的后继之间的边全部删去。

于是，我们可以得到一份初步的拓扑排序代码：

#include <iostream>
#include <cstdio> 
#include <vector>
#define maxn 5003
using namespace std;

int N /*节点数量*/,M /*边的数量*/ ;
vector<int> Edge[maxn];
/*我个人习惯使用vector存图，vector<int> *Edge[i]表示i的所有后继*/ 
int In[maxn]/*前驱数组，记录每个节点的实时前驱数量*/; 
int G[maxn],tot;/*拓扑序列数组*/

int First,End;
/*临时变量*/

int main()
{
    scanf("%d%d",&N,&M);
    for(int i = 1 ; i<= M ; i++)
    {
        scanf("%d%d",&First,&End);
        Edge[First].push_back(End);
        /*读入并添加一条 First -> End 的边*/
        In[End]++;
        /*记录前驱数量*/ 
    }
    while(tot < N)
    {
        for(int i = 1 ; i<= N ; i++)
        {
            if(In[i] == 0)
            {
                G[++tot] = i;
                for(int Now : Edge[i])
                    In[Now]--;
                /*遍历 vector<int> *Egde[i]，改变i的所有后继的前驱数组数量*/
            }
        }
    }
    for(int i = 1 ; i<= N ; i++)
        printf("%d ",G[i]);
    puts(""); 
    return 0;
}

输入数据：

输出（拓扑序列）：

1 2 3 4 5 6

解释：

该有向图为如下：

可以尝试对比理解。

代码优化：

当你理解以后，就会发现这份代码慢得~~kou~~难以忍受，稍微卡一卡，就可以到 \mathcal{O(n^2)} 的时间复杂度。所以，我们需要优化。

仔细思考，当一个节点从有前驱变成无前驱，只有可能是它的最后一个前驱被加入了序列的那一瞬间！那么我们只要抓住这个“瞬间”，结合 dijkstra 的优化方式，不难想到使用队列优化。

具体请看优化代码：

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#define maxn 5003
using namespace std;

int N,M;
vector<int> Edge[maxn];
int In[maxn];
int G[maxn],tot;

int First,End;
queue<int> Q;

int main()
{
    scanf("%d%d",&N,&M);
    for(int i = 1 ; i<= M ; i++)
    {
        scanf("%d%d",&First,&End);
        Edge[First].push_back(End);
        In[End]++;
    }
    for(int i = 1 ; i<= N ; i++)
        if(In[i] == 0)
            Q.push(i);
    while(!Q.empty())
    {
        int u = Q.front();
        Q.pop();
        G[++tot] = u;
        for(int Now : Edge[u])
        {
            In[Now]--;
            if(In[Now] == 0)
                 Q.push(Now);
        }
    }
    for(int i = 1 ; i<= tot ; i++)/*tot = n*/
        printf("%d ",G[i]);
    puts("");
    return 0;
}

通过这种方式，可以省掉不必要的遍历，对于稀疏图，可以大大减少时间复杂度，降低了被卡的可能性。（不过很遗憾，对于完全图，它会退化成朴素算法

三、此题该怎么做？

非常简单，求拓扑序列的同时记录每道题完成的天数，当序列求到编号为 K 的题时，输出完成天数并结束程序即可。若程序一直执行到最后，输出-1。

具体看代码：

#include <iostream>
#include <cstdio>
#include <vector>
#include <bitset> 
#include <queue>
#define maxn 5003
using namespace std;

vector<int> Edge[maxn];
bitset<maxn> Avai;
int N,K,p;
int R;
int In[maxn];

int First,End,Num;

queue<pair<int,int> > Q;

int main()
{
    while(!Q.empty())
        Q.pop();
    scanf("%d%d%d",&N,&K,&p);
    for(int i = 1 ; i<= p ; i++)
    {
        scanf("%d",&Num);
        Avai[Num] = true;
        Q.push({Num,0});
    }
    scanf("%d",&R);
    for(int i = 1 ; i<= R ; i++)
    {
        scanf("%d%d",&End,&Num);
        while(Num--)
        {
            scanf("%d",&First);
            Edge[First].push_back(End);
            In[End]++;
        }
    }
    while(!Q.empty())
    {
        pair<int,int> u = Q.front();
        Q.pop();
        int ID = u.first;
        int Day = u.second;
        if(!Avai[ID])
            continue;
        if(ID == K)
        {
            printf("%d\n",Day);
            return 0;
        }
        for(int End: Edge[ID] )
        {
            In[End]--;
            if(In[End] == 0)
            {
                Avai[End] = true;
                Q.push({End,Day+1});
            }
        }
    }
    puts("-1");
    return 0;
}

写在最后：

首先，此题较为简单，

建议评 \textcolor{#FFC116}{Popularization/Enhancement-}。

其次，