首页 > 代码库 > 拓扑排序1.奖金
拓扑排序1.奖金
【题目描述】
由于无敌的凡凡在2005年世界英俊帅气男总决选中胜出，Yali Company总经理Mr.Z心情好，决定给每位员工发奖金。公司决定以每个人本年在公司的贡献为标准来计算他们得到奖金的多少。
于是Mr.Z下令召开m方会谈。每位参加会谈的代表提出了自己的意见：“我认为员工a的奖金应该比b高！”Mr.Z决定要找出一种奖金方案，满足各位代表的意见，且同时使得总奖金数最少。每位员工奖金最少为100元。
【输入】
第一行两个整数n,m，表示员工总数和代表数；
以下m行，每行2个整数a,b，表示某个代表认为第a号员工奖金应该比第b号员工高。
【输出】
若无法找到合法方案，则输出“-1”；否则输出一个数表示最少总奖金。
输入输出样例
reward.in
2 1
1 2
reward.out
201
【数据范围】
80％的数据满足n<=1000，m<=2000；
100％的数据满足n<=10000，m<=20000。
个人解析:
这道题就是拓扑排序。排的过程中，把自己所须的经费加上.
把最便宜的那个人作为起点。之后开始拓扑。每次加钱的时候可以先加基数100，之后那一层拓扑（同时有几个入度为0的点）的时候把相应的 个数＊层数。就是第几个加钱的，与第几个加钱的人数的乘积。
1 #include<cstdio> 2 #include<algorithm> 3 #include<string.h> 4 using namespace std; 5 struct node{ 6 int next; 7 int v; 8 }edge[20010]; 9 int queue[10010];10 int head[10010],r[10010],c[10010];11 int n,m,cnt;12 void add(int x,int y){13 edge[++cnt].next=head[x];14 edge[cnt].v=y;15 head[x]=cnt;16 }17 int main()18 {19 scanf("%d%d",&n,&m);20 int x,y;21 memset(head,-1,sizeof(head));22 for(int i=1;i<=m;i++)23 {24 scanf("%d%d",&x,&y);25 add(y,x);26 r[x]++;27 c[y]++;28 }29 int t,tot=0,money=0,k=0;30 while(tot<n){31 t=0;//当前层里的入度为0的个数。 32 for(int i=1;i<=n;i++)33 {34 if(r[i]==0){35 t++;tot++;money+=100;36 queue[0]++; //队列[0]放的是队列里元素的个数 37 queue[queue[0]]=i;38 r[i]=-1;39 }40 }41 if(t==0){ //出现环。 42 printf("Poor Xed");43 return 0;44 }45 money=money+k*t; 46 k++;//层数++。 47 for(int i=1;i<=queue[0];i++){48 for(int j=head[queue[i]];j!=-1;j=edge[j].next)49 {50 r[edge[j].v]--; //该点的下一个点的入度--。 51 }52 }53 queue[0]=0; //队列清空。 54 }55 printf("%d",money);56 return 0;57 }
拓扑排序1.奖金
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。