HDU 4857 逃生 (优先队列+反向拓扑)
2024-10-12 11:25:22
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4857
解题报告:有n个点,有m个条件限制,限制是像这样的,输入a b,表示a必须排在b的前面,如果不能确定两个数谁排在前面则尽量把小的排在前面。
首先把出度为0的点加入到优先队列中,然后每次用优先队列中弹出的点去更新其它点的出度,更新的同时如果又有其它点的出度为0的话又加到优先队列中,
最后按照从优先队列中出队的反序输出就可以了。我还是不懂为什么按照入度为0然后加入到优先队列然后正序输出这样为什么不行。希望有懂的人可以告诉我。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int maxn = +; priority_queue<int> que;
vector<int> vt[maxn];
int du[maxn],ans[maxn];
int main()
{
int T,n,m;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
int u,v;
for(int i = ;i <= n;++i)
vt[i].clear();
memset(du,,sizeof(du));
while(m--)
{
scanf("%d%d",&u,&v);
du[u]++;
vt[v].push_back(u);
}
for(int i = ;i <= n;++i) //把出度为0的先加到优先队列中
if(!du[i]) que.push(i);
int f = n - ;
while(!que.empty())
{
int s = que.top();
que.pop();
ans[f--] = s;
int len = vt[s].size();
for(int i = ;i < len;++i)
{
int tt = vt[s][i];
du[tt]--;
if(du[tt] == ) que.push(tt);
}
}
for(int i = ;i < n;++i)
printf(i == ? "%d":" %d",ans[i]);
puts("");
}
return ;
}
最新文章
- Linux与user和group相关文件分析
- 开源库Magicodes.ECharts使用教程
- Criteria 和 DetachedCriteria的区别与使用
- ubuntu下如何用命令行运行deb安装包
- jquery 字符串转dom对象及对该对象使用选择器查询
- 转: JSP中include指令和include动作的区别
- Python mongoDB 的简单操作
- jquery validate.js表单验证的基本用法入门
- spoj SORTBIT - Sorted bit squence
- Selenium2+Python自动化测试实战
- 天坑 之 JSP编译错误
- C# winform调用WebBrowser经典怪问题总结
- 每天一个linux命令(47)--scp命令
- Android Things 专题6 完整的栗子:运用TensorFlow解析图像
- 销售行业ERP数据统计分析都有哪些维度?
- First Unique Character in a String
- C# 串口操作系列(5)--通讯库雏形
- VueJs(6)---V-on指令
- JavaScript Hoisting(提升)
- ENode, 领域模型,DDD
热门文章
- Windows Phone8 中如何引用 SQLite 数据库
- [USACO2005][POJ3045]Cow Acrobats(贪心)
- Linux中使用crontab命令定时执行shell脚本或其他Linux命令
- 问问题_为什么关闭浏览器后Session会失效
- 【CodeForces 625C】K-special Tables
- 【BZOJ-2809】dispatching派遣 Splay + 启发式合并
- cogs896 圈奶牛
- 新建的 web 工程 有红色的惊叹号
- groovy–流程控制
- udp 内网穿透 互发消息