$P1317. 奖金$

🚀️ 题解思路

如果直接建立图，那么就会发生这种情况：

$$a \to b \to c \to d$$

由题意，得：

员工 $a$ 的奖金应该比 $b$ 高

但是我们不知道 $a$ 的值且题目说： 每位员工奖金 最少 为 $100$ 元 所以得出一个结论 —— 要 反向 建图

---

考虑 $bfs$，这里给一个拓扑排序的模板：

queue<int> q;
void topsort()
{
	for(int i = 1; i <= n; i++){
		if(d[i] == 0) q.push(i);//入度为0
	}
	while(!q.empty()){//bfs
		int u = q.front();
		q.pop();
		ans[++cnt] = u;//存储拓扑序列
		for(int i = 0; i < g[u].size(); i++){
			int v = g[u][i];
			d[v]--;
			if(d[v] == 0) q.push(v);
		}
	}
	if(cnt != n) cout << "the graph has cycle." << "\n";//环 
	else for(int i = 1; i <= cnt; i++) cout << ans[i] << " ";
}

先定义 $f_i$ 表示 $i$ 名员工的奖金

可是有一种特殊情况：

反向建图后

$$c \to b \to a$$ $$d \to a$$

那么可以得知 $a$ 的奖金应为 $102$ 元，而不是 $101$元。所以可以得到状态转移方程：

$$f[i] = max(f[i], f[u] + 1);$$

其中的 $u$ 是 $i$ 的邻界点。

若无法找到合法方案，也就是说有环，输出 -1。

记得 $memset$

代码如下：

#include <bits/stdc++.h>
using namespace std;
int maxn;
int n, m, cnt;
queue<int> q;
int ind[20005];
bool vis[20005];
int money[20005];
vector<int> g[20005];
int main()
{
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		int a, b;
		cin >> a >> b;
		g[b].push_back(a);
		ind[a]++;
	} 
	for(int i = 1; i <= n; i++){
		if(ind[i] == 0) q.push(i);
	}
	for(int i = 1; i <= n; i++) money[i] = 100; 
	while(!q.empty()){
		cnt++;
		int p = q.front();
		q.pop();
		for(int i = 0; i < g[p].size(); i++){
			int val = g[p][i];
			money[val] = max(money[val], money[p] + 1);
			ind[val]--;
			if(ind[val] == 0) q.push(val);
		}
	}
	if(cnt != n){
		cout << -1;
		return 0;
	}
	for(int i = 1; i <= n; i++) maxn += money[i];
	cout << maxn; 
	return 0;
}