A28838. 奖金
填空题
困难
知识点
题目描述
奖金
题目描述
由于无敌的凡凡在2005年世界英俊帅气男总决选中胜出，Yali Company总经理Mr.Z心情好，决定给每位员工发奖金。公司决定以每个人本年在公司的贡献为标准来计算他们得到奖金的多少。
于是Mr.Z下令召开m方会谈。每位参加会谈的代表提出了自己的意见：“我认为员工a的奖金应该比b高！”Mr.Z决定要找出一种奖金方案，满足各位代表的意见，且同时使得总奖金数最少。每位员工奖金最少为100元。
输入
第一行两个整数n,m，表示员工总数和代表数；
以下m行，每行2个整数a,b，表示某个代表认为第a号员工奖金应该比第b号员工高。
输出
若无法找到合理方案，则输出“Poor Xed”；否则输出一个数表示最少总奖金。
输入样例
2 1
1 2输出样例
201提示
数据规模
80％的数据满足：n≤1000，m≤2000；
100％的数据满足：n≤10000，m≤20000。
参考答案
#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;
}答案解析
拓扑排序
每个人是一个顶点。
如果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)。
统计算法进行过程中入度变为0的顶点数量num
如果num < n，则未完成拓扑排序，有向图中存在环，无法安排奖金，输出"Poor Xed"。
如果num == n，则完成了拓扑排序，有向图无环。输出所有顶点的奖金加和。
上一题
下一题