洛谷 P3243 [HNOI2015]菜肴制作

题目描述
知名美食家小 A被邀请至ATM 大酒店,为其品评菜肴。 ATM 酒店为小 A 准备了 N 道菜肴,酒店按照为菜肴预估的质量从高到低给予1到N的顺序编号,预估质量最高的菜肴编号为1。

由于菜肴之间口味搭配的问题,某些菜肴必须在另一些菜肴之前制作,具体的,一共有 M 条形如”i 号菜肴’必须’先于 j 号菜肴制作“的限制,我们将这样的限制简写为<i,j>。

现在,酒店希望能求出一个最优的菜肴的制作顺序,使得小 A能尽量先吃到质量高的菜肴:

也就是说,

(1)在满足所有限制的前提下,1 号菜肴”尽量“优先制作;

(2)在满足所有限制,1号菜肴”尽量“优先制作的前提下,2号菜肴”尽量“优先制作;

(3)在满足所有限制,1号和2号菜肴”尽量“优先的前提下,3号菜肴”尽量“优先制作

;(4)在满足所有限制,1 号和 2 号和 3 号菜肴”尽量“优先的前提下,4 号菜肴”尽量“优先制作;

(5)以此类推。

例1:共4 道菜肴,两条限制<3,1>、<4,1>,那么制作顺序是 3,4,1,2。

例2:共5道菜肴,两条限制<5,2>、 <4,3>,那么制作顺序是 1,5,2,4,3。

例1里,首先考虑 1,因为有限制<3,1>和<4,1>,所以只有制作完 3 和 4 后才能制作 1,而根据(3),3 号又应”尽量“比 4 号优先,所以当前可确定前三道菜的制作顺序是 3,4,1;接下来考虑2,确定最终的制作顺序是 3,4,1,2。

例 2里,首先制作 1是不违背限制的;接下来考虑 2 时有<5,2>的限制,所以接下来先制作 5 再制作 2;接下来考虑 3 时有<4,3>的限制,所以接下来先制作 4再制作 3,从而最终的顺序是 1,5,2,4,3。 现在你需要求出这个最优的菜肴制作顺序。无解输出”Impossible!“ (不含引号,首字母大写,其余字母小写)

输入格式
第一行是一个正整数D,表示数据组数。 接下来是D组数据。 对于每组数据: 第一行两个用空格分开的正整数N和M,分别表示菜肴数目和制作顺序限制的条目数。 接下来M行,每行两个正整数x,y,表示”x号菜肴必须先于y号菜肴制作“的限制。(注意:M条限制中可能存在完全相同的限制)

输出格式
输出文件仅包含 D 行,每行 N 个整数,表示最优的菜肴制作顺序,或者“Impossible!“表示无解(不含引号)。

这是一道非常裸的拓扑排序。
我们先介绍一下什么是拓扑排序:
拓扑排序:给出一些节点,每个点出现之前都有一定的条件,也就是说在一个点出现之前,某个特定的点必须出现过。
这道题我本来是想直接用一个小根堆实现的,但是他要求1,2,3…先出现的条件,有的数据会gg,(随便举)
因为字典序是贪心的,如果前面的一位能小就尽可能的小,并不保证1出现尽量靠前。但是如果建一个反图,求一个反向字典序最大的拓扑序呢?那么就会有大的数尽量靠前的情况出现,于是交小的数尽量靠后,于是反过来就是小的数尽量靠前了(强行解释.jpg)

顺便学了下vector的用法,真香

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#define int long long 
using namespace std;
const int N=100005;
int a[N];
int in[N];
int n,m,d,cnt; 
vector<int>edge[100010],ans;
priority_queue<int>q;//大根堆 
inline int read(){
   
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){
   x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline void clea(){
   
	for(int i=1;i<=n;i++){
   
		edge[i].clear();
		in[i]=0;
	}
	while(!q.empty()) q.pop();
	ans.clear();
}
inline void tuopu(){
   
	while(!q.empty()){
   
		int dmf=q.top();
		q.pop();
		cnt++;
		ans.push_back(dmf);
		for(vector<int>::iterator it=edge[dmf].begin();it!=edge[dmf].end();it++){
   
			in[*it]--;
			if(!in[*it]) q.push(*it);
		}
	}
	if(cnt<n)puts("Impossible!");
	else{
   
		for(vector<int>::iterator it=ans.end()-1;it!=ans.begin();it--)
		printf("%d ",*it);
		printf("%d\n",*ans.begin());
	// printf("\n");
	}
}
main(){
   
	d=read(); 
	while(d--){
   
		n=read();m=read();
		clea();
		for(int i=1;i<=m;i++){
   
			int x,y;
			x=read();y=read();
			edge[y].push_back(x);
			in[x]++;
		}
		cnt=0;
		for(int i=1;i<=n;i++){
   
			if(!in[i]) q.push(i);
		}
		tuopu();
	}
	return 0;
} 

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
2022-12-01 12:52
广州商学院_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-16 02:48
门头沟学院_2022
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
01-07 18:24
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
2022-12-22 00:27
中南大学_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 1 评论
分享

全站热榜

正在热议