$2023山東ICPC省賽ProblemB.建筑公司$

比賽鏈接：Dashboard - The 13th Shandong ICPC Provincial Collegiate Programming Contest - Codeforces

官方題解：B - 建筑公司 - SUA Wiki

題意

題目給出若干中工種和每類工種的人數，然后給出若干項工程，每項工程的性質有：

1. 完成該項工程所需的各工種人數。
2. 完成該項工程后可以增加的每類工種人數。要求求出最多能夠完成多少項工程？

每項工程需要完成的時間忽略不計，可以理解為只要各工種人數滿足該工程所需人數，則和獲取此工程的增加人數，并且需要完成該工程的人數不會消耗。

思路

我們可以簡化題目，看作每項工程只需一類工種，那么自然很容易想到拓撲排序。

但是這道題稍微復雜一些，每項工程需要的工種種類多一些。

我們考慮對于每項工程建立拓撲圖，并且把每項工程所需的各工種人數看作是連接在工程上的節點，若現有工種人數大于該工程的所需人數，則將該工種所代表的節點從該工程上去掉；若某工程的入度為$0$，則表示該工程所有需要的工人數量都滿足，那么就可以完成該工程，并且將該工程可增加的工種人數加上。

需要注意的是：本題的重點是如何刪除每個工程上的節點（工程需要的工種人數）？

• 可行的做法是：可以將每個工種數量不滿足的工程給存起來然后排序。
• 具體排序規則為：將需要該工種的工程根據需要的數量從小到大排序。
• 容易知道，若當前度不為$0$的節點，只有其工種人數增加后，該節點才可能被消除。

注意點已詳細注釋在標程代碼中，以便理解。

標程

#include<bits/stdc++.h>using namespace std;#define IOS ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
#define LL long long 
#define ULL unsigned long long 
#define PII pair<int, int>
#define lowbit(x) (x & -x)
#define Mid ((l + r) >> 1)
#define ALL(x) x.begin(), x.end()
#define endl '\n'
#define fi first 
#define se secondconst int INF = 0x7fffffff;
const int Mod = 1e9 + 7;
const int N = 2e5 + 10;int g, n, k, m, t, u;
map<int, int> a;//a存每個工種的人數
map<int, priority_queue<PII, vector<PII>, greater<PII>>> q;//存每個工種數量不滿足的工程
vector<PII> v[N];//v存每個工程可增加的每個工種人數
vector<int> c(N);//c存每個工程缺的工種數量
queue<int> qu;//存當前入度為0的工程void Solved() {cin >> g;for(int i = 1; i <= g; i ++ ) {//記錄各工種人數cin >> t >> u;a[t] = u;}cin >> n;for(int i = 1; i <= n; i ++ ) {cin >> m;for(int j = 1; j <= m; j ++ ) {//每項工程需要人數cin >> t >> u;if(a[t] < u) {             //只保存還需要的人數就行（找出初始入度為0的工程）c[i] ++;q[t].push({u, i});}}cin >> k;for(int j = 1; j <= k; j ++ ) {//每項工程增加人數cin >> t >> u;v[i].push_back({t, u});}}for(int i = 1; i <= n; i ++ ) {//先將入度為0的工程處理掉if(!c[i]) qu.push(i);}int res = 0;//q[i]表示對于第i種工人人數，不滿足哪些工程//qu中存放當前入度為0的工程while(!qu.empty()) {int i = qu.front(); qu.pop();res ++;//對于每個工種，只有其數量增加，才能完成其他工程，所以只需要判斷增加的工種即可for(auto f : v[i]) {t = f.fi, u = f.se;a[t] += u;            //添加當前工程可增加的各工種人數while(!q[t].empty()) {//判斷當前所有需要工種t的工程PII p = q[t].top();if(a[t] >= p.fi) {c[p.se] --;q[t].pop();//若當前工程需要的人都滿足，則該工程入度為0if(c[p.se] == 0) qu.push(p.se);} else {//對于當前工種，若工程不滿足，則先跳過break;}}}}cout << res << endl;
}signed main(void) {IOSint ALL = 1; // cin >> ALL;while(ALL -- ) Solved();// cout << fixed;//強制以小數形式顯示// cout << setprecision(n); //保留n位小數return 0;
}