HDU 4857 逃生 （优先队列+反向拓扑）

时间：2025-02-11 18:07:56

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4857

解题报告：有n个点，有m个条件限制，限制是像这样的，输入a  b,表示a必须排在b的前面，如果不能确定两个数谁排在前面则尽量把小的排在前面。

首先把出度为0的点加入到优先队列中，然后每次用优先队列中弹出的点去更新其它点的出度，更新的同时如果又有其它点的出度为0的话又加到优先队列中，

最后按照从优先队列中出队的反序输出就可以了。我还是不懂为什么按照入度为0然后加入到优先队列然后正序输出这样为什么不行。希望有懂的人可以告诉我。

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<queue>

 #include<vector>

 using namespace std;

 const int maxn = +;

 priority_queue<int> que;

 vector<int> vt[maxn];

 int du[maxn],ans[maxn];

 int main()

 {

     int T,n,m;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d%d",&n,&m);

         int u,v;

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

         vt[i].clear();

         memset(du,,sizeof(du));

         while(m--)

         {

             scanf("%d%d",&u,&v);

             du[u]++;

             vt[v].push_back(u);

         }

         for(int i = ;i <= n;++i) //把出度为0的先加到优先队列中

         if(!du[i]) que.push(i);

         int f = n - ;

         while(!que.empty())

         {

             int s = que.top();

             que.pop();

             ans[f--] = s;

             int len = vt[s].size();

             for(int i = ;i < len;++i)

             {

                 int tt = vt[s][i];

                 du[tt]--;

                 if(du[tt] == ) que.push(tt);

             }

         }

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

         printf(i == ? "%d":" %d",ans[i]);

         puts("");

     }

     return ;

 }

相关文章