凡科建站电话咨询,软件开发流程简介,搭建网页游戏服务器,长沙外贸公司奖金
ssl 1325
题目大意#xff1a;
有n个人#xff0c;某个人要比另外一个人的工资高#xff08;工资最低为100#xff0c;最少多1元#xff09;#xff0c;问最少发多少工资
原题#xff1a;
题目描述
由于无敌的凡凡在2005年世界英俊帅气男总决选中胜出#x…奖金
ssl 1325
题目大意
有n个人某个人要比另外一个人的工资高工资最低为100最少多1元问最少发多少工资
原题
题目描述
由于无敌的凡凡在2005年世界英俊帅气男总决选中胜出Yali Company总经理Mr.Z心情好决定给每位员工发奖金。公司决定以每个人本年在公司的贡献为标准来计算他们得到奖金的多少。 于是Mr.Z下令召开m方会谈。每位参加会谈的代表提出了自己的意见“我认为员工a的奖金应该比b高”Mr.Z决定要找出一种奖金方案满足各位代表的意见且同时使得总奖金数最少。每位员工奖金最少为100元。
输入
两个整数n,m表示员工总数和代表数 以下m行每行2个整数a,b表示某个代表认为第a号员工奖金应该比第b号员工高。
输出
若无法找到合法方案则输出“-1”否则输出一个数表示最少总奖金。
输出样例
2 1
1 2输入样例
201数据范围
80的数据满足n1000m2000 100的数据满足n10000m20000。
解题思路
这就是拓扑排序先按顺序拓扑排序一遍中途顺便DP以100为低值因为要求最小所以一定是上一个数1然后有多个条件是就要求最大的
代码
#includequeue
#includecstdio
#includecstring
#includeiostream
using namespace std;
int n,m,x,y,h,tot,sum,rd[10500],head[10500],ans[10500];
struct rec
{int to,next;
}a[20500];
void topsort()//拓扑排序
{queueintd;for (int i1;in;i)if (!rd[i]) d.push(i),ans[i]100;//入度为0的while(!d.empty()){hd.front();d.pop();for (int ihead[h];i;ia[i].next){rd[a[i].to]--;ans[a[i].to]max(ans[h]1,ans[a[i].to]);//取最大if (!rd[a[i].to])//入度为0{rd[a[i].to]--;d.push(a[i].to);}}}
}
int main()
{scanf(%d %d,n,m);for (int i1;im;i){scanf(%d %d,x,y);a[tot].tox;a[tot].nexthead[y];head[y]tot;rd[x];}topsort();for (int i1;in;i)if (rd[i]0) sumans[i];//符合else{sum-1;//存在环break;}printf(%d,sum);
}
