[Leaf] [P3243] 菜肴制作

p3243-[hnoi2015]-菜肴制作---洛谷">P3243 [HNOI2015] 菜肴制作 - 洛谷

1. 题面梗概

中译中: 给出一堆 $A$ 必须在 $B$ 之前的约束条件，在满足约束条件的前提下，让编号小的菜肴尽可能靠前。

2. 逻辑推导

这是一个典型的偏序问题，又是前驱后继类约束，我们可以从 拓扑排序 入手分析。

2.1 贪心

既然编号小的菜肴尽可能靠前，那不等价于字典序最小吗？

但这恰恰是贪心的陷阱。我们可以假设这样一组反例：$n = 3$，约束条件为 $3 \to 1$。

如果是字典序最小，那么就是 $2, 3, 1$。但实际上应该让 $1$ 靠前一点，也就是 $3, 1, 2$。

显然，这个 $2$ 没有约束条件，我们正着贪心没法预知后面的顺序，不妨反着来？

2.2 逆向思维

既然 小的靠前 不好处理，不妨换成 大的靠后 来处理。

那么我们只要反着建图就行了，同时可以用一个堆来优化这个查询过程，每次找到最大的那个值放进拓扑序中，最后翻转即可。

注意特判不可能的情况即可。

2.3 补充

为什么反着贪心就可以呢？如前面反例，我们不确定 $2$ 应该在什么位置，我们只确定了 $3 \to 1$。

在正着贪心的过程中，我们只能去比较 $2$ 和 $3$ 的关系，从而忽视了后面 $1$，因此才会出现这个问题。

3. 代码实现

▶

AcCode

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 1e5 + 5;

vector< int > adj[maxn];
int indeg[maxn];
int n, m;

void solve( )
{
    cin >> n >> m;

    for( int i = 1; i <= n; ++ i ) 
    {
        adj[i].clear( );
        indeg[i] = 0;
    }

    for( int i = 1; i <= m; ++ i )
    {
        int u, v;
        cin >> u >> v;
        adj[v].push_back( u );
        indeg[u] ++;
    }

    priority_queue< int > pq;
    for( int i = 1; i <= n; ++ i )
    {
        if( indeg[i] == 0 ) pq.push( i );
    }

    vector< int > ans;
    while( !pq.empty( ) )
    {
        int u = pq.top( );
        pq.pop( );
        ans.push_back( u );
        for( int v : adj[u] )
        {
            indeg[v] --;
            if( indeg[v] == 0 ) pq.push( v );
        }
    }

    if( ans.size( ) != n )
    {
        cout << "Impossible!" << '\n';
        return;
    }

    reverse( ans.begin( ), ans.end( ) );
    for( int u : ans ) cout << u << ' ';
    cout << '\n';
}

int main( )
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int _t = 1;
    cin >> _t;
    while( _t -- ) solve( );
    return 0;
}

4. 复盘

• 复杂度分析：建图 $O(M)$，拓扑排序 $O((N+M) \log N)$。瓶颈在优先队列。

• 碎碎念：这题贪心比较害人，需要考虑到反向解决问题。

• 关联笔记：拓扑排序 | 贪心策略