拓扑排序+小根堆

古城微笑少年丶 2022-09-11 02:29 121阅读 0赞

[题目链接][Link 1]

#include<iostream>
    #include<cstdio>
    #include<string>
    #include<ctime>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<stack>
    #include<climits>
    #include<queue>
    #include<map>
    #include<set>
    #include<sstream>
    #include<cassert>
    #include<bitset>
    #include<list>
    #include<unordered_map>
    using namespace std;
    #define ll long long
    #define pii pair<ll,ll>
    #define N 50007
    int n, s;
    vector<int>f[N],vec[N];//后置关卡、该道具必过的关卡
    int d[N];
    struct node
    { 
        int a,b,c,d;//暴力通过需要的属性值、该关卡所需的必过道具、可以增加的属性值，可以获得的必过道具
    }p[N];
    bool vis[N],vis1[N];//记录i点过否、记录i号必过道具是否拥有
    
    void bfs()
    { 
        priority_queue<pii, vector<pii>, greater<pii> >q;
        // 小根堆
        q.push({ p[1].a,1}); // 暴力通过值，以及编号（第几个点）
        
        while (q.size())
        { 
            auto t=q.top(); // 所需暴力值最小的排在最前面
            q.pop();
            
            if(s<=t.first) // 最小的暴力通过不了，无解
            { 
                cout<<"No"<<endl;
                return;
            }
            if(vis[t.second]) // 判断第i点的记录
                continue;
                
            s+=p[t.second].c; // 通过这一点，属性值增加
            vis[t.second]=1; // 标记这一点过了
            if(!vis1[p[t.second].d]) // 通过这一点的获得的道具
            { 
                vis1[p[t.second].d]=1; // 标记获得的必过道具
                for(auto it:vec[p[t.second].d]) // 对于用必过该道具能过的关卡
                { 
                    p[it].a=0;  // 用第二种方法过，前驱直接置为0
                    if(d[it]==0) // 如果入度为0，则是不需要前驱关卡，且有了必过道具
                    // 用第二种方法过。
                    { 
                        q.push({ p[it].a,it});
                    }
                }
            }
            for(auto it:f[t.second]) // 这一个点的后置关卡，如果入度为0， 加入小根堆
            { 
                if(--d[it]==0)
                { 
                    q.push({ p[it].a,it});
                }
            }
        }
        cout<<"Yes"<<endl;
    }
    int main()
    { 
        ios::sync_with_stdio(0);
        cin>>n>>s;
        for(int i=1;i<=n;i++)
        { 
            cin>>p[i].a>>p[i].b; // 暴力和必备关卡
            vec[p[i].b].push_back(i); // 该道具能过的关卡
        }
        for(int i=1;i<=n;i++)
        { 
            cin>>p[i].c>>p[i].d; // 增加的暴力值，获得关卡
        }
        for(int i=1;i<=n;i++)
        { 
            int k;
            cin>>k;
            for(int j=1;j<=k;j++)
            { 
                int id;
                cin>>id;
                f[i].push_back(id); // 后置关卡
                d[id]++; // 后置关卡的入度+1， 为了topsort()
            }
        }
        for(int i=1;i<=n;i++)
        { 
            if(i==1&&d[i]) // 第一关的入度不是0，无解
            { 
                cout<<"No"<<endl;
                return 0;
            }
            if(i!=1&&!d[i]) // 关卡没有前置关卡，无解
            { 
                cout<<"No"<<endl;
                return 0;
            }
        }
        bfs();
        return 0;
    }

[Link 1]: https://ac.nowcoder.com/acm/contest/20263/G