首页 > 分享 > P3243 [HNOI2015] 菜肴制作题解

P3243 [HNOI2015] 菜肴制作题解

花匠小妙招
2024-12-15 00:10

前言

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

题意

有道菜肴，编号为。有个条件，形如，表示菜肴必须在菜肴之前制作。需求出一个菜肴的制作顺序，满足：

在满足所有限制的前提下，号菜肴尽量优先制作。

在满足所有限制，号菜肴尽量优先制作的前提下，号菜肴尽量优先制作。

以此类推。

如果无解，输出 Impossible!。

形式化

给定个点，条边的有向图，需求出其拓扑序，满足在拓扑序合法的前提下，点优先且点在点优先的前提下优先。无解输出 Impossible!。

解法

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

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

它的正确拓扑序为：。

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

我们来看这个例子：

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

关于时间，我采用的是 DFS，对于每个入度为的节点，跑一遍 DFS，但是这样的最坏时间复杂度为，直接被卡飞。

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

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

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

这样做的朴素时间复杂度为，但是可以使用 bitset 优化一下，可以将时间复杂度降为，算了一下单次大概的样子，数据组数小于等于，那么就是，稍微卡一卡即可通过。

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

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

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

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

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

AC Code

#include<bits/stdc++.h>#define int long longusing 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;}

本文作者：Luckies的小窝

本文链接：https://www.cnblogs.com/Luckies/p/17962644/P3243