题解 P3243 【[HNOI2015]菜肴制作】

这道题看起来就是个裸的拓扑排序，抄上模板就能AC。

上面这种想法一看就不现实，然鹅我第一次还真就这么写了，然后被随意hack。

我们需要注意一句话：

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

这句话什么意思呢？

看上去它是说想要一个字典序最小的排列，但我们可以发现，题目并不是强求质量高一定先，而是有一个宽限范围（可能我讲的比较玄学）。

解决方案是贪心地把大的放在末尾，那么最后一定是最优解。

所以我们跑一个字典序最大的拓扑就可以了。

字典序最大就是反着跑一遍字典序最小。

AC代码如下：

820ms 133668kb

 #include<bits/stdc++.h>

 using namespace std;

 namespace StandardIO {

     template<typename T>inline void read (T &x) {

         x=;T f=;char c=getchar();

         for (; c<''||c>''; c=getchar()) if (c=='-') f=-;

         for (; c>=''&&c<=''; c=getchar()) x=x*+c-'';

         x*=f;

     }

     template<typename T>inline void write (T x) {

         if (x<) putchar('-'),x*=-;

         if (x>=) write(x/);

         putchar(x%+'');

     }

 }

 using namespace StandardIO;

 namespace Solve {

     const int N=;

     int T,n,m,cnt;

     int indeg[N],ans[N];

     vector<int>graph[N];

     inline void toposort () {

         int temp[N];

         priority_queue<int>q;

         memcpy(temp,indeg,sizeof(indeg));

         while(!q.empty())q.pop();

         for (register int i=; i<=n; ++i) {

             if (temp[i]==) q.push(i);

         }

         while (!q.empty()) {

             int v=q.top();q.pop();

             ans[++cnt]=v;

             for (register int i=; i<graph[v].size(); ++i) {

                 int to=graph[v][i];

                 temp[to]--;

                 if (temp[to]==) q.push(to);

             }

         }

     }

     inline void solve () {

         read(T);

         while (T--) {

             read(n),read(m);

             cnt=,memset(indeg,,sizeof(indeg));

             for (register int i=; i<=n; ++i) {

                 graph[i].clear();

             }

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

                 int x,y;

                 read(x),read(y);

                 indeg[x]++;

                 graph[y].push_back(x);

             }

             toposort();

             if (cnt!=n) puts("Impossible!");

             else {

                 for (register int i=n; i>=; --i) write(ans[i]),putchar(' ');

                 putchar('\n');

             }

         }

     }

 }

 using namespace Solve;

 int main () {

 //    freopen(".in","r",stdin);

 //    freopen(".out","w",stdout);

     solve();

 }

巴特西

题解 P3243 【[HNOI2015]菜肴制作】

最新文章

热门文章