这道题的贪心思路可真是很难证明啊......

对于<i,j>的限制(i必须在j之前),容易想到topsort,每次在入度为0的点中选取最小的。但这种正向找是错误的,题目要求的是小的节点尽量往前,并不是字典序最小。<i,j>中i肯定大于j,这样建的图中小的节点是靠后的,当然不行;那我们考虑反向建图,那么小的节点就靠前了,因为是反向建图,我们要让大的节点尽量往前,最后倒着输出,那么小的节点自然就靠前了。

有种重要的思路就是正的不行那就反着来,考场上实在不能证明,那就多举几个例子看是否正确。

建立大根堆,再反向图中优先选择大的节点。

有环时就是无解的情况,ans节点数量小于n。

 1 #include<bits/stdc++.h>
2 using namespace std;
3 const int N=1e5+5;
4 int T,n,m,in[N];
5 vector<int> a[N],ans;
6
7 int main(){
8 scanf("%d",&T);
9 while(T--){
10 memset(in,0,sizeof(in));ans.clear();
11 for(int i=0;i<N;i++) a[i].clear();
12 scanf("%d%d",&n,&m);
13 for(int i=1;i<=m;i++){
14 int x,y;scanf("%d%d",&x,&y);
15 a[y].push_back(x);in[x]++;
16 }
17 priority_queue<int> q;//大根堆
18 for(int i=1;i<=n;i++)
19 if(!in[i]) q.push(i);//入度为0的点加入
20 while(!q.empty()){
21 int v=q.top();q.pop();
22 ans.push_back(v);
23 for(int i=0;i<a[v].size();i++){
24 in[a[v][i]]--;
25 if(!in[a[v][i]]) q.push(a[v][i]);
26 }
27 }
28 if(ans.size()!=n) puts("Impossible!");
29 else{
30 reverse(ans.begin(),ans.end());
31 for(int i=0;i<ans.size();i++) printf("%d ",ans[i]);
32 puts("");
33 }
34 }
35 return 0;
36 }

最新文章

  1. 基于Struts2CRUD的质量属性
  2. python装饰器通俗易懂的解释!
  3. vijos1431[noip2007]守望者的逃离(背包动规)
  4. 梳理一下JS的基本语法
  5. 如何设置jquery的ajax方法为同步
  6. 夺命雷公狗---node.js---4net模块(上)
  7. Oracle DB SQL 性能分析器
  8. MySQL数据库最大连接数
  9. UI4_UIToolBar
  10. MP3的频率、比特率、码率与音质的关系
  11. Dreamweaver安装jQuery插件jQuery_API.mxp
  12. WinForm窗体设置
  13. CentOS6.3下搭建vsftpd(采用虚拟用户设置)
  14. LoadLibrary 失败 GetLastError 126
  15. 基于TypeScript的FineUIMvc组件式开发(概述)
  16. java与C++变量初始化的对比
  17. Dynamics CRM2011/2013 站点地图sitemap的翻译
  18. 同步手绘板——android端取色
  19. [Laravel] 04 - Blade templates
  20. mui---自定义页面打开的方向

热门文章

  1. HTTP协议-工作原理及消息结构
  2. H5移动端实现一键复制或长摁复制
  3. git和提交分支
  4. python 操作xml、html文件
  5. python自带gui插件tkinter使用小结
  6. 4. 利用MySQL Shell安装部署MGR集群 | 深入浅出MGR
  7. 轮询以及webSocket与socket.io原理
  8. 分库分表ShardingSphere-JDBC笔记整理
  9. Dubbo源码(八) - 负载均衡
  10. docker compose搭建redis7.0.4高可用一主二从三哨兵集群并整合SpringBoot【图文完整版】