Luogu3243 [HNOI2015]菜肴制作

tony102

2020 年 11 月 09 日

1152 次浏览

暂无评论

684字数

题解

[Link](https://www.luogu.com.cn/problem/P3243)

## Description

有$n$道菜，编号越小的越美味（最美味的是$1$号菜品）。现在给出一些形如$(i,j)$的限制，表示$i$号菜品必须在$j$号菜品之前制作。要求出一个最优的菜肴的制作顺序，使得Karry5307能尽量先吃到美味的菜肴。无解输出Impossible!

## Sol

如果你是贪心地求字典序小的，Karry5307不一定能吃到尽量先地吃到最美味的菜品。

比如说共4 道菜肴，两条限制$(3,1)$、$(4,1)$，那么制作顺序是 $3,4,1,2$。但是你贪心就会变成$2,3,4,1$但是如果反过来处理，建一个反图，求一个反向字典序最大的拓扑序。那么就会有大的数尽量靠前的情况出现，于是交小的数尽量靠后，于是反过来就是小的数尽量靠前了。

## Code

果然代码环节还是我最喜欢的

```cpp
#include <bits/stdc++.h>
using namespace std;

const int SIZE = 1e5 + 5;

int q, n, m, num;
int head[SIZE], deg[SIZE];

struct node {
	int to, nxt;
} edge[SIZE];

namespace ae86 {
	const int bufl = 1 << 15;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	inline int read() {
		int a = 0, b = 1, c = fetch();
		while (!isdigit(c))b ^= c == '-', c = fetch();
		while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
		return b ? a : -a;
	}
}
using ae86::read;

inline void addEdge(int u, int v)
{
	edge[++ num].to = v, edge[num].nxt = head[u];
	head[u] = num;
}

inline void top()
{
	std::priority_queue < int > q;
	std::vector < int > ans;
	for (int i = 1; i <= n; ++ i) {
		if (!deg[i]) q.push(i);
	}
	while (!q.empty()) {
		int u = q.top(), v;
		ans.push_back(u);
		q.pop();
		for (int i = head[u]; i; i = edge[i].nxt) {
			v = edge[i].to;
			-- deg[v];
			if (!deg[v]) q.push(v);
		}
	}
	if ((int) ans.size() != n) puts("Impossible!");
	else {
		for (auto i = ans.end() - 1; i != ans.begin() - 1; -- i) printf("%d ", *i);
		putchar('\n');
	}
}

int main()
{
	// freopen("code.in", "r", stdin);
	// freopen("code.out", "w", stdout);
	q = read();
	while (q --) {
		n = read(), m = read();
		for (int i = 1, u, v; i <= m; ++ i) {
			u = read(), v = read();
			addEdge(v, u); ++ deg[u];
		}
		top();
		num = 0;
		memset(head, 0, sizeof(head));
		memset(deg, 0, sizeof(deg));
	}
	return 0;
}
```

最后修改：2021 年 09 月 04 日