【HNOI2015】菜肴制作
2024-09-25 07:57:24
题面
题解
这道题目首先可以想到拓扑排序,但是肯定不是字典序最小的排列。
比如说,有\(4\)种菜,限制为\(2 \to 4, 3 \to 1\),那么如果求字典序最小的排列会算出\((2, 3, 1, 4)\),但是答案显然是\((3, 1, 2, 4)\)。
于是,正难则反,发现如果最后一个数字在合法的范围内尽可能的大,那么就会更优。
我们就可以求字典序反序最大的排列。
于是建反图,跑拓扑排序即可,这里的拓扑排序要用到堆。
代码
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<queue>
#define RG register
#define file(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);
#define clear(x, y) memset(x, y, sizeof(x))
inline int read()
{
int data = 0, w = 1; char ch = getchar();
while(ch != '-' && (!isdigit(ch))) ch = getchar();
if(ch == '-') w = -1, ch = getchar();
while(isdigit(ch)) data = data * 10 + (ch ^ 48), ch = getchar();
return data * w;
}
const int maxn(3e5 + 10);
std::priority_queue<int> heap;
struct edge { int next, to; } e[maxn];
int head[maxn], e_num, n, m, deg[maxn], T, cnt, ans[maxn];
inline void add_edge(int from, int to)
{
e[++e_num] = (edge) {head[from], to};
head[from] = e_num; ++deg[to];
}
int main()
{
T = read();
while(T--)
{
clear(head, 0); e_num = 0;
clear(deg, 0);
n = read(); m = read();
int f = 0; cnt = 0;
for(RG int i = 1, x, y; i <= m; i++)
{
x = read(), y = read(), add_edge(y, x);
if(x == y) f = 1;
}
if(f) { puts("Impossible!"); continue; }
for(RG int i = 1; i <= n; i++) if(!deg[i]) heap.push(i);
while(!heap.empty())
{
int x = heap.top(); heap.pop(); ans[++cnt] = x;
for(RG int i = head[x]; i; i = e[i].next)
{
int to = e[i].to;
if(!(--deg[to])) heap.push(to);
}
}
if(cnt < n) puts("Impossible!");
else { for(RG int i = n; i; i--) printf("%d ", ans[i]); puts(""); }
}
return 0;
}
最新文章
- 每天一个linux命令(25):linux文件属性详解
- Macosx 安装 ionic 成功教程
- TYVJ 1074 武士风度的牛
- oracle变量的定义和使用【转】
- iOS-CALayer图片淡入淡出动画
- 火狐浏览器插件Modify Headers伪造IP地址
- Web---自己写的一个简单云相册~
- Dbentry4.2连接MSSQL
- 使用Javascript获取当前目录的绝对路径
- xml转换为json格式时,如何将指定节点转换成数组 Json.NET
- patch 请求时,关于id的报错问题
- SaaS的先鋒:多合一讯息处理器
- hdu1011(树形背包)(提供一个特殊样例)
- Linux命令行下载工具
- Kafka、RabbitMQ、RocketMQ等消息中间件的对比 —— 消息发送性能和区别
- android studio中编译单个文件
- uva11235 FrequentValues (ST表)
- 【WIN10】WIN2D——圖層
- JAVA-JSP内置对象之request对象参数
- Java学习---Collection的学习
热门文章
- 解决 There are no resources that can be added or removed from the server
- Script:when transaction will finish rollback
- [翻译] BezierString
- EditPlus 自动格式化js、html、css,以EditPlus 文本编辑器v3.41(1145)为例
- Python静态方法实现单实例模式
- 转载:从程序员的角度看ASCII, GB2312, UNICODE, UTF-8
- php命名空间的设计思想和缺点
- CSS3 Transform变形理解与应用
- HDU5343:MZL&#39;s Circle Zhou(SAM,记忆化搜索DP)
- Hadoop学习之路(十三)MapReduce的初识