专栏文章
题解:P3243 [HNOI2015] 菜肴制作
P3243题解参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性,并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @miqo5ukl
- 此快照首次捕获于
- 2025/12/04 07:59 3 个月前
- 此快照最后确认于
- 2025/12/04 07:59 3 个月前
做法
首要想到字典序最小的拓扑序,发现题目要求的是数字小的尽量靠前,so 打开题解 略微思索一二,发现当大的数尽量靠后,那么小的数也会尽量靠前。所以反向建图跑字典序最大的拓扑序!!! 过于巧妙!!!
代码:
CPP#include<cstdio>
#include<queue>
#include<stack>
using namespace std;
int len;
int n,m;
int a,b;
int in[100005];
int num[100005],pre[100005],last[100005],cnt;
priority_queue <int> q;
stack <int> ans;
void ddxyz(){
cnt=0;
while(!q.empty()){
q.pop();
}
while(!ans.empty()){
ans.pop();
}
for(int i=1;i<=100000;i++){
in[i]=num[i]=pre[i]=last[i]=0;
}
}
void add(int x,int y){
++cnt;
num[cnt]=y;
pre[cnt]=last[x];
last[x]=cnt;
}
void tp(){
for(int i=1;i<=n;i++){
if(in[i]==0){
q.push(i);
}
}
while(!q.empty()){
int fro=q.top();
q.pop();
ans.push(fro);
for(int i=last[fro];i;i=pre[i]){
in[num[i]]--;
if(in[num[i]]==0){
q.push(num[i]);
}
}
}
}
int main(){
scanf("%d",&len);
while(len--){
ddxyz();
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d",&a,&b);
add(b,a);
in[a]++;
}
tp();
if(ans.size()<n){
printf("Impossible!\n");
}
else{
while(!ans.empty()){
printf("%d ",ans.top());
ans.pop();
}
printf("\n");
}
}
return 0;
}
相关推荐
评论
共 0 条评论,欢迎与作者交流。
正在加载评论...