【题解 && 拓扑思维】 C - Building Company

题目描述:

---

分析：

对于每一个项目，需要满足几个条件，对于每一个条件，表示为第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;
}

原文地址：https://blog.csdn.net/huang_ke_hai/article/details/135949717

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！