具体代码
时间: 2023-07-02 19:16:38 浏览: 56
好的,下面是这道题的具体代码实现。
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXN 1005
#define INF 0x3f3f3f3f
int n, m, ans; // 员工总数、代表数、最小奖金总数
int in_degree[MAXN], out_degree[MAXN], graph[MAXN][MAXN], reward[MAXN];
void topsort() {
int q[MAXN], head = 0, tail = -1;
for (int i = 1; i <= n; ++i) {
if (in_degree[i] == 0) {
q[++tail] = i;
reward[i] = 100;
}
}
while (head <= tail) {
int u = q[head++];
for (int v = 1; v <= n; ++v) {
if (graph[u][v]) {
if (--in_degree[v] == 0) {
q[++tail] = v;
}
if (reward[v] < reward[u] + 100) {
reward[v] = reward[u] + 100;
}
}
}
}
for (int i = 1; i <= n; ++i) {
ans += reward[i];
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < m; ++i) {
int a, b;
scanf("%d%d", &a, &b);
if (!graph[b][a]) {
graph[b][a] = 1;
++in_degree[a];
++out_degree[b];
}
}
topsort();
if (out_degree[1] > 0) {
printf("POOR!\n");
} else {
printf("%d\n", ans);
}
return 0;
}
```
代码中使用了邻接矩阵来存储图,使用in_degree数组来记录每个点的入度,out_degree数组来记录每个点的出度,reward数组来记录每个点的奖金,ans来记录所有员工的最小奖金总数。在输入过程中,对于每个代表认为的员工之间的关系,构建一条从b到a的有向边,表示b应该比a的奖金高。然后使用拓扑排序的方式来求解各个员工的奖金,具体的求解方式是,对于每个入度为0的点,将其奖金初始化为100,然后依次遍历其所有的出边,如果到达的点的奖金小于当前点的奖金+100,则将该点的奖金更新为当前点的奖金+100。最后,遍历所有员工的奖金,求和得到最小奖金总数。如果存在任意一个员工的出度不为0,说明存在环,即无法找到合理的奖金方案,输出"POOR!"。否则,输出最小奖金总数。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)