题目描述:
分析：
对于每一个项目，需要满足几个条件，对于每一个条件，表示为第i项工作需要有几个人做。
这几个条件全部满足后，这个项目就可以收入囊下，同时获得新的员工
对于每一个项目的几个条件，我们其实可以当作一些约束，当这些约束全部满足，那么就可以加入新员工继续拓展。
这种结构似乎有点熟悉？
没错，就是拓扑结构。
对于每一个项目，我们将他拆分成k(k表示当前项目所需要的工作数)项工作
对于每一项工作，我们开一个堆，记录当前工作需要的人数以及当前的项目的编号
同时用一个队列来存储当前我们拥有的工位，同时需要记录每一个工位的员工数
模拟拓扑结构，从当前队列中拥有的工位出发，将当前工位堆中能处理的工作全部处理完，同时记录一下如果当前工位是当前项目所需要的最后一个工位，那么就将当前项目所能获得的新工位放入队列中继续拓展。
直到无法继续拓展为止
这题还需要注意的一个点是工位编号有1e9是比较大的，用数组桶存不下
哈希一下即可
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair < int , int > pii;
#define mp make_pair
const int N = 1e5+100;
map < int , int > ma;
int a[N],cnt;
bool vi[N];
priority_queue < pii , vector < pii > , greater < pii > > q[N];
int n;
int m,k;
int ans = 0;
queue < int > Q;
struct Node{
int k;
vector < int > a,b;
}b[N];
int num[N];
signed main(){
cin>>n;
for (int i = 1; i <= n; i++){
int x,y;
cin>>x>>y;
if (ma.count(x) == 0) ma[x] = ++cnt;
if (!vi[ma[x]]) Q.push(ma[x]),vi[ma[x]] = 1;
a[ma[x]]+=y;
}
cin>>m;
for (int i = 1; i <= m; i++){
cin>>k;
num[i] = k;
for (int j = 1,x,y; j <= k; j++){
cin>>x>>y;
if (ma.count(x) == 0) ma[x] = ++cnt;
q[ma[x]].push(mp(y,i));//将每一个项目拆成k项工作
}
cin>>b[i].k;
for (int j = 1,x,y; j <= b[i].k; j++){
cin>>x>>y;
if (ma.count(x) == 0) ma[x] = ++cnt;
b[i].a.push_back(ma[x]); b[i].b.push_back(y);
}
}
for (int i = 1; i <= m; i++)
if (num[i] == 0){
//先把能加入的加入
ans++;
for (int j = 1; j <= b[i].k; j++){
int x = b[i].a[j-1] , y = b[i].b[j-1];
if (!vi[x]) Q.push(x),vi[x] = 1;
a[x]+=y;
}
}
while (Q.size()){
int x = Q.front(); Q.pop(); vi[x] = 0;
while (q[x].size()){
//处理当前工位
int xx = q[x].top().first , yy = q[x].top().second;
if (xx > a[x]) break;//处理不了了就退出
q[x].pop();
num[yy]--;
if (num[yy] == 0){
//约束条件全部满足
ans++;
for (int i = 1; i <= b[yy].k; i++){
int X = b[yy].a[i-1] , Y = b[yy].b[i-1];
if (!vi[X]) Q.push(X),vi[X] = 1;
a[X]+=Y;
}
}
}
}
cout<<ans;
return 0;
}
