专栏文章

题解: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 条评论,欢迎与作者交流。

正在加载评论...