【题目链接】
ybt 1352 【例4-13】奖金
【题目考点】
1. 图论：拓扑排序
【解题思路】
解法1：拓扑排序
每个人是一个顶点。
如果a奖金比b高，应该先确定b的奖金数，再确定a的奖金。
因此可以这样定义边：如果b的奖金比a高，那么存在有向边<a, b>。
设数组money，顶点i的奖金为money[i]。
图中入度为0的顶点的奖金为100。
使用Kahn算法进行拓扑排序：
拓扑排序的过程中，顶点u访问邻接点v，存在弧<u, v>，v的奖金应该比u的奖金至少高1，应该用money[u]+1更新money[v]，即moeny[v] = max(money[v], moeny[u]+1)。文章来源：https://www.toymoban.com/news/detail-571572.html
统计算法进行过程中入度变为0的顶点数量num文章来源地址https://www.toymoban.com/news/detail-571572.html
- 如果num < n，则未完成拓扑排序，有向图中存在环，无法安排奖金，输出"Poor Xed"。
- 如果num == n，则完成了拓扑排序，有向图无环。输出所有顶点的奖金加和。
【题解代码】
#include<bits/stdc++.h>
using namespace std;
#define N 10005
int n, m, degIn[N], money[N];//money[i]：员工i获得的钱数
vector<int> edge[N];
bool topoSort()//返回是否有环
{
int num = 0;
queue<int> que;
for(int v = 1; v <= n; ++v)
if(degIn[v] == 0)
{
que.push(v);
money[v] = 100;
}
while(que.empty() == false)
{
int u = que.front();
que.pop();
num++;
for(int v : edge[u])
{
money[v] = max(money[v], money[u]+1);
if(--degIn[v] == 0)
que.push(v);
}
}
return num < n;
}
int main()
{
int a, b, sum = 0;
cin >> n >> m;
for(int i = 1; i <= m; ++i)
{
cin >> a >> b;
edge[b].push_back(a);
degIn[a]++;
}
bool hasRing = topoSort();
if(hasRing)
cout << "Poor Xed";
else
{
for(int v = 1; v <= n; ++v)
sum += money[v];
cout << sum;
}
return 0;
}
到了这里，关于信息学奥赛一本通 1352 【例4-13】奖金的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
