洛谷 P3243 【[HNOI2015]菜肴制作】

先吐槽一下这个难度吧，评的有点高了，但是希望别降，毕竟这是我能做出来的不多的紫题了（狗头）。

大家上来的第一反应应该都是啊，模板题，然后兴高采烈的打了拓补排序的板子，然后搞个小根堆，按照字典序输出就可。但是这样过不了第三组样例，为什么呢？不告诉你呢因为题目让你的仅仅是1后面快点跟2,2后面快点跟3而已，并没有让我们用字典序输出，问题lei了，如何按照题目的要求搞呢？把第三组样例推一下，可以发现\(<5,2>,<4,3>\)都是由于后面的2,3决定的，再推下其他的样例，可以发现一组关系都是根据这组关系较小的那个数字决定的，因为题目让数字小的尽量靠前，而排序不正确也就是因为在前面的那些大的数字干扰了我们去确定后面的那些小的数字，既然前面大的数字会干扰后面小的数字，那我们直接从后面的大的入手，把大的尽量靠后即可，所以直接反向建图，用大根堆维护当前入度为0的序列，最后把拓补排序反过来输出就行。而根据上面的经验，反向建图后再反向输出，加个大根堆，就是让大的尽量靠后，而前面的不会去干扰后面的，所以这样做是正确的（这个地方把它讲明白我想了好久啊，求个赞不过分吧）。

代码就简单了：

#include <bits/stdc++.h>

using namespace std;

int n , tot , T , m;

int f[100010] , ans[100010];

vector<int> e[100010];

int main(){

	cin >> T;

	while(T--){

		cin >> n >> m;

		memset(f , 0 , sizeof(f));

		for(int i = 1; i <= 100000; i++) e[i].clear();	//清空

		tot = 0;

		for(int i = 1; i <= m; i++){

			int x , y;

			cin >> x >> y;

			f[x]++;

			e[y].push_back(x);	//反向建图

		}

		priority_queue<int> q;

		for(int i = 1; i <= n; i++)

			if(!f[i]) q.push(i);

		while(!q.empty()){

			int x = q.top();

			q.pop();

			ans[++tot] = x;

			for(int i = 0; i < e[x].size(); i++){

				f[e[x][i]]--;

				if(!f[e[x][i]]) q.push(e[x][i]);

			}

			e[x].clear();

		}

		if(tot != n){

			cout << "Impossible!" << endl;

			continue;

		}

		for(int i = n; i >= 1; i--) cout << ans[i] << " ";	//反向输出

		cout << endl;

	}

	return 0;

}

巴特西

洛谷 P3243 【[HNOI2015]菜肴制作】

最新文章

热门文章