首页 > 其他分享 >南沙信奥老师解题:1352:【例4-13】奖金

南沙信奥老师解题:1352:【例4-13】奖金

时间:2024-09-02 19:25:27浏览次数:13  
标签:13 信奥 degree int 1352 cnt 员工 奖金 money

 【题目描述】

由于无敌的凡凡在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;
int degree[10001],n,m,money[10001],cnt=0;
vector<int> e[10001];
stack<int> q;
bool TopoSort()
{
	while(!q.empty())
	{
		int i=q.top();
		q.pop();
		cnt++;
		for(int j=0;j<e[i].size();j++)
		{	
			int v=e[i][j];	
			money[v]=max(money[v],money[i]+1); 
			//拓扑排序的过程中,顶点i访问邻接点v,存在弧<i, v>,i的奖金应该比v的奖金至少高1,应该用money[i]+1更新money[v]
			degree[v]--;
			if(degree[v]==0)
				q.push(v);	
		}	
	}
	return cnt<n?false:true;
}
int main()
{
	cin>>n>>m;	
	for(int i=1;i<=m;i++)
	{
		int a,b;
		cin>>a>>b;
		e[b].push_back(a); //要注意a的奖金比b高,即b的入度为0. 即100  b->a 
		degree[a]++;
	}
	for(int i=1;i<=n;i++)
		if(degree[i]==0)
		{
			q.push(i);
			money[i]=100;
		}
	if(TopoSort())
	{
		int sum=0;
		for(int i=1;i<=n;i++)
			sum+=money[i];
		cout<<sum;
	}
	else
		cout<<"Poor Xed"; 
	return 0;
}

 

标签:13,信奥,degree,int,1352,cnt,员工,奖金,money
From: https://www.cnblogs.com/nanshaquxinaosai/p/18393346

相关文章

  • 高密度、高速卡边缘连接器,ME1005610201091、ME1005610203071、ME1005613401311、ME100
    系列概述MiniCoolEdge是一款0.60mm高密度、高速卡边缘连接器,适用于新一代小型系统。这种精细间距解决方案支持多种板对板应用,如直角、夹层/共面,并提供电缆互连选件。这些连接器符合SFF-TA-1002、GenZ、EDSFF和OCPNIC3.0规范。常见应用包括固态驱动器、网络接口卡和......
  • 最优化(13):近似点梯度法、Nesterov算法
    6.1  近似点梯度法        6.1.1 邻近算子(proximaloperator):主要介绍proximaloperator的相关定义和性质        6.1.2  近似点梯度法:给出了proximalgradientmethod算法框架        6.1.3 应用举例:LASSOproblem和Low-rankmatrixcomp......
  • python入门每日一练2023/2/13
    python入门每日一练,可以提高您的python水平,今天是2月13日,上一课的答案是foriinrange(1,len(strb)+1):ifstrb[i]==p:print(i)qq="qq"www="www"com=".com"如何组成www.qq.com网址?(难度★☆☆☆☆)......
  • AP2813宽输入电压5-80V 双路降压恒流LED芯片_外围简单内置功率管驱动IC
    产品描述AP2813是一款双路降压恒流驱动器,高效率、外围简单、内置功率管,适用于5-80V输入的高精度降压LED恒流驱动芯片。内置功率管输出最大功率可达12W,最大电流1.2A。AP2813一路直亮,另外一路通过MODE1切换全亮,爆闪。AP2813工作频率固定在150KHZ左右,同时内置抖频电......
  • AP2813宽输入电压5-80V 双路降压恒流LED芯片_外围简单内置功率管驱动IC
    产品描述AP2813是一款双路降压恒流驱动器,高效率、外围简单、内置功率管,适用于5-80V输入的高精度降压LED恒流驱动芯片。内置功率管输出最大功率可达12W,最大电流1.2A。AP2813一路直亮,另外一路通过MODE1切换全亮,爆闪。AP2813工作频率固定在150KHZ左右,同时内置抖频......
  • 安卓13拦截home功能 监听home键 禁用home键
    总纲android13rom开发总纲说明目录1.前言2.问题分析3.代码分析4.代码修改5.编译6.彩蛋1.前言  经常遇到客户监听某个按键的需求,其实有些功能APP本身就可以处理的,......
  • 周赛413场 个人总结
    第1题 代码 """根据a的ascii码值是97奇数黑色的规律是:a1是97+1=偶数b2是98+2=偶数c1是99+1=偶数d2是100+2=偶数...所以,偶数为黑色===白色的规律a2=97+2=奇数b1=98+1=奇数....所以,奇数为白色"""classSolution:defche......
  • CMake构建学习笔记13-opencv库的构建
    OpenCV(OpenSourceComputerVisionLibrary)是一个开源的计算机视觉和机器学习软件库,旨在提供一个跨平台的、易于使用的、快速执行的计算机视觉接口。如果只是简单的使用,其实不必要像笔者这样使用源代码进行构建,直接使用官方提供的二进制安装包即可。一般来说,需要从源代码进行构建......
  • SDKD 2024 Summer Training Contest F2(The 13th Shandong ICPC Provincial Collegiat
    A-Orders题意每天能生产k个产品的工厂有n个订单,第i个订单是在a_i天交b_i个产品,问能否交付。思路订单按日期排序,记录剩下的商品.代码#define_CRT_SECURE_NO_WARNINGS#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintmxn=1e6+5......
  • 2024 年 13 个适用于 Linux 的最佳照片图像编辑器
      2024年13个适用于Linux的最佳照片图像编辑器   在本文中,我回顾了各种Linux发行版上可用的一些最佳照片编辑软件。这些不是唯一可用的照片编辑器,但却是Linux用户最流行和最常用的照片编辑器之一。1.GIMP首先,在列表中,我们有 GIMP,一个免费、开源、跨平台......