ICPC第13届山东省赛

题面

思路

模拟一下拓扑序列的思想，把需求抽象成一种边，每一种尚未满足的需求都是一个入度，按顺序把解决的需求对应的项目入度减一，定义一个队列，把所有入度为0的项目全部加进去，当这个队列为空时，所有可解决的项目均被记录，退出循环输出答案即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int inf32 = 1e9 + 7;
constexpr int inf64 = 1e9 + 7;
const int N=2e5;
typedef pair<int,int> PII;
map<int,int>have;                                           //当前有的员工的对应数量
map<int,priority_queue<PII,vector<PII>,greater<PII>>> need; //所有需求，及对应的任务标号，用优先队列存
vector<PII>reward[N];                                       //解决某个任务之后获得的奖励人数
int din[N];
int x,n;
int ans;                    
void solve(){
    cin>>x;
    for(int i=1;i<=x;i++){
        int a,b;
        cin>>a>>b;
        have[a]+=b;
    }
    cin>>n;
    queue<int>accord;
    for(int i=1;i<=n;i++){
        int m1,m2;
        cin>>m1;                            //第i项目有m1个需求
        for(int j=1;j<=m1;j++){     
            int a,b;    
            cin>>a>>b;    
            if(have[a]<b){                  //只有当前的需求尚未被满足，才增加一个入度
                din[i]++;
                need[a].push({b,i});        //员工标号为a的增加一个数量为b的需求，该需求对因项目i
            }    
        }
        cin>>m2;                    
        for(int j=1;j<=m2;j++){
            int a,b;
            cin>>a>>b;
            reward[i].push_back({a,b});     //reward[i]表示解决项目i后获得的所有奖励
        }
        if(!din[i]) accord.push(i);         //若入度为0则已经被解决
    }
    while(!accord.empty()){                 //已经被解决的条件
        int idx=accord.front();
        accord.pop();
        ans++;
        for(auto [id,num]:reward[idx]){     //遍历得到的新员工可以解决的需求，若出现新入度为0的点，加入队列
            have[id]+=num;
            while(!need[id].empty()){
                if(need[id].top().first<=have[id]){
                    din[need[id].top().second]--;
                    if(din[need[id].top().second]==0) accord.push(need[id].top().second);
                    need[id].pop();
                }
                else break;
            }
        }
    }
    cout<<ans<<endl;
}
signed main(){
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
}