首页 > 代码库 > hdu 4857 逆拓扑+大根堆(priority_queue)

hdu 4857 逆拓扑+大根堆(priority_queue)

题意:排序输出:在先满足定约束条件下(如 3必需在1前面,7必需在4前面),在满足:1尽量前,其次考虑2,依次。。。。。(即有次约束)。

开始的时候,只用拓扑,然后每次在都可以选的时候,优先考虑小的,其实没什么简单,如 图(3-->1,2)这样输出是2.3.1,正确应该是 3 1 2,因为 1要尽量前(都满足第一约束)。

参考他人思路结合自己理解:因为这样的弊端就是没有考虑这种情况:图中:若我的“子孙”中,有的比你次优先,虽然现在我们都可以输出,但是要考虑我的子代,若我的子代有次优先级比你高的,必需是我输出后,子代输出,你再输出。所以自然想到dfs查子代次优先级,这是一种方法,但是建逆图就可以解决这个问题,走逆图的拓扑序,选的时候选大的数,保存,由于逆图中,孩子次优先级高的必在前面了,直接可以和你比,按“大”的保存。

用优先队列刚好解决问题。


#include<iostream>
#include<stack>
#include<vector>
#include<queue>
using namespace std;
int n,m;int ind[32000];
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n>>m;
        vector<vector<int> >e(n+1);
        for(int i=0;i<=n;i++)
               ind[i]=0;
        int a,b;
        while(m--)
        {
            cin>>a>>b;
            e[b].push_back(a);
            ind[a]++;
        }
        priority_queue<int>q;
        for(int i=1;i<=n;i++)
        {
            if(ind[i]==0)
              q.push(i);
        }
        vector<int>ans;
        while(!q.empty())
        {
            int cur=q.top();
            q.pop();
            ans.push_back(cur);
            for(int i=0;i<e[cur].size();i++)
            {

                int v=e[cur][i];
                ind[v]--;
                if(ind[v]==0)
                   q.push(v);
            }
        }
        for(int i=ans.size()-1;i>=0;i--)
        {
            if(i==0)cout<<ans[i]<<endl;
            else cout<<ans[i]<<" ";
        }
    }
    return 0;
}