首页 > [HNOI2015]菜肴制作

钱逸凡

发表于 2020-10-30 15:38:32

本题坑点题目没有给数据规模，我去别的oj网站上查了，是 100%的数据满足N,M<=100000,D<=3 解题思路 “看到x要先于y”这类字的时候，第一反应就是拓扑排序（不知道拓扑排序点这里），但是有一个问题，如果用拓扑排序，我们只能得到字典序最小的方案，不能满足题目要求的使得小展开全文

默默然诶

发表于 2022-07-16 16:37:19

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int head[N],inc[N],ans[N]; int T,n,m,num,a1,a2; struct ty{ int y,next; }ed 展开全文

在刷题的单身狗很开心

发表于 2023-11-01 09:06:54

//反向建边，在正常的拓扑排序里面我们只能按照起始的点去寻找最大或最小的字符序列， //但是在题目当中要求尽量先吃到质量高的菜肴，那么这就关系到终点了。 //所以我们可以采用反向建边的方式，去求一个字符序列最大的，这样就实现了尽量先吃到质量高的菜肴。 #include <bits/s 展开全文

夜语声烦-

发表于 2023-02-06 18:43:40

#include <iostream> #include <cstring> #include <queue> #include <vector> using namespace std; const int N = 1e5 + 10; int 展开全文

Z_L_G

发表于 2025-07-11 23:10:04

#反向建边 #拓扑排序题意有n个菜，m个条件约束条件(a,b)，表a必须在b之前除了约束条件外，要保证序号小的的尽可能先做在满足所有限制的前提下，1 号菜肴”尽量“优先制作；在满足所有限制，1号菜肴”尽量“优先制作的前提下，2号菜肴”尽量“优先制作；以此类推。例：共4 道菜肴，两条限展开全文

查看本题

查看本题讨论

等你来战

查看全部

相关比赛