洛谷P3243 [HNOI2015]菜肴制作 (拓扑排序/贪心)
2024-09-08 11:23:07
这道题的贪心思路可真是很难证明啊......
对于<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 }
最新文章
- 基于Struts2CRUD的质量属性
- python装饰器通俗易懂的解释!
- vijos1431[noip2007]守望者的逃离(背包动规)
- 梳理一下JS的基本语法
- 如何设置jquery的ajax方法为同步
- 夺命雷公狗---node.js---4net模块(上)
- Oracle DB SQL 性能分析器
- MySQL数据库最大连接数
- UI4_UIToolBar
- MP3的频率、比特率、码率与音质的关系
- Dreamweaver安装jQuery插件jQuery_API.mxp
- WinForm窗体设置
- CentOS6.3下搭建vsftpd(采用虚拟用户设置)
- LoadLibrary 失败 GetLastError 126
- 基于TypeScript的FineUIMvc组件式开发(概述)
- java与C++变量初始化的对比
- Dynamics CRM2011/2013 站点地图sitemap的翻译
- 同步手绘板——android端取色
- [Laravel] 04 - Blade templates
- mui---自定义页面打开的方向