P3243 [HNOI2015] 菜肴制作题解

Luckies · 2023-09-25 15:28:03 · 题解

前言

今天考试考到这道题，挂惨了。

题意

有 n 道菜肴，编号为 1 \sim n。有 m 个条件，形如 (i, j)，表示菜肴 i 必须在菜肴 j 之前制作。需求出一个菜肴的制作顺序，满足：

在满足所有限制的前提下，1 号菜肴尽量优先制作。
在满足所有限制，1 号菜肴尽量优先制作的前提下，2 号菜肴尽量优先制作。
\dots\dots
以此类推。

如果无解，输出 Impossible!。

形式化

给定 n 个点，m 条边的有向图，需求出其拓扑序，满足在拓扑序合法的前提下，点 1 优先且点 i(i \in |V|, i \ne 1) 在点 i - 1 优先的前提下优先。无解输出 Impossible!。

解法

首先给出一个错解，这东西是我考场胡的，但是可能对后面有帮助。

对于每一个点 x，求出它往后的所有路径上经过的点的最小权值 mi_x（包括 x）。然后使用堆进行拓扑排序，以 mi_x 为第一关键字，x 为第二关键字，就像这样:

它的正确拓扑序为：1, 3, 4, 5, 2。

但是，它是错误的，不管是正确性还是时间。

我们来看这个例子：

在这个图中，正确的拓扑序为 6, 5, 2, 4, 3, 1，可这种方法跑出来的答案是 6, 4, 3, 5, 2, 1。可以发现，5 和 4 这两个点的 mi 是相等的，并且有公共的终点。这个时候，只要把两条路径中间的点调一下，这样贪心就是错误的。

关于时间，我采用的是 DFS，对于每个入度为 0 的节点，跑一遍 DFS，但是这样的最坏时间复杂度为 \Theta(\frac{n^2}{4})，直接被卡飞。

我们可以对这个错解修改一下。

对于每个点 x，它的子节点为 y_1, y_2, \dots, y_k，在拓扑序中选择的先后顺序是这样的：将 y_1, y_2, \dots, y_k 往后的路径经过的点排序，然后按这些序列的字典序大小来选择。

按照刚刚的错解，错误的原因是多条路径上的最小值可能相等。那就一个一个从小到大比较啊，这样就是对的了。

这样做的朴素时间复杂度为 \Theta(n^2)，但是可以使用 bitset 优化一下，可以将时间复杂度降为 \Theta(\frac{n^2}{w})，算了一下单次大概 3 \cdot 10^7 的样子，数据组数小于等于 3，那么就是 9 \cdot 10^7，稍微卡一卡即可通过。

接下来讲时间复杂度正确的算法。

可以发现，我们刚才的分析都是正着分析的，但是这样是不好维护的，因为字典序小不一定是最优解。

那么我们倒着想。小的要在前面，那么大的就要在后面。在拓扑序合法的情况下，尽量把大的放在后面。那么这样就可以把小的数都尽量靠前。

那么，只需要在反图上跑字典序最大的拓扑序，然后反转一下即为答案。

字典序最大的拓扑序可以使用大根堆。

AC Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
int t, n, m, in[N], IN[N], mi[N];
vector<int> e[N], ans;
void init()
{
    ans.clear();
    for(int i = 1; i <= n; i++)
        e[i].clear();
    memset(in, 0, sizeof(in));
    memset(IN, 0, sizeof(IN));
    // memset(mi, 0x3f, sizeof(mi));
    return;
}
void topo_sort()
{
    priority_queue<int> q;
    for(int i = 1; i <= n; i++)
        if(!in[i])
            q.push(i);
    int cnt = 0;
    while(!q.empty())
    {
        int x = q.top();
        q.pop();
        cnt++;
        ans.push_back(x);
        for(auto y : e[x])
            if(!--in[y])
                q.push(y);
    }
    if(cnt != n)
    {
        cout << "Impossible!\n";
        return;
    }
    reverse(ans.begin(), ans.end());
    for(auto i : ans)
        cout << i << " ";
    cout << "\n";
    return;
}
void solve()
{
    cin >> n >> m;
    init();
    for(int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        e[y].push_back(x);
        in[x]++;
    }
    // for(int i = 1; i <= n; i++)
    //     cout << mi[i] << " ";
    // cout << "\n";
    // for(int i = 1; i <= n; i++)
    //     for(int j = i + 1; j <= n; j++)
    //     if(!vis[i][j])
    //     {
    //         vis[i][j] = vis[j][i] = true;
    //         e[i].push_back(j);
    //         in[j]++;
    //     }
    topo_sort();
    return;
}
signed main()
{
    // freopen("dishes.in", "r", stdin);
    // freopen("dishes.out", "w", stdout);
    cin >> t;
    while(t--)
        solve();
    return 0;
}

P3243 [HNOI2015] 菜肴制作 题解

前言

题意

形式化

解法

AC Code

P3243 [HNOI2015] 菜肴制作题解