您的位置:威尼斯官方网站 > 威尼斯正规官网 > 不然输出叁个数表示最少总奖金

不然输出叁个数表示最少总奖金

发布时间:2019-08-24 19:00编辑:威尼斯正规官网浏览(60)

    奖金,奖金土耳其语

    【难点呈报】   由于无敌的凡凡在二零零七年世界英俊英美男子总决选中胜出,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<=一千,m<=两千;100%的数量知足n<=一千0,m<=贰仟0。 【算法解析】   首先构图,若存在条件“a的钱比b多”则从b引一条有向指向a;然后拓扑排序,若无法实现排序则意味难题无解(存在圈);若能够博得完全的拓扑体系,则按类别顺序实行递推:     设f[i]代表第i私人商品房能拿的起码奖金数;     首先全体f[i]=100(标题中加以的最小值);    然后依据拓扑顺序考查每一个点i,若存在有向边(j,i),则表示f[i]必须比f[j]大,因而大家令f[i]威尼斯官方网站, = Max { f[i] , f[j] 1 }就能够;  递推完毕之后全数f[i]的值也就规定了,而答案就等于f[1] … f[n]。   部分大额必要用差分约束系统那么些笔者其实不会

     1 #include<iostream>
     2 #include<cstdio>
     3 #include<cstring>
     4 #include<stack>
     5 using namespace std;
     6 struct node
     7 {
     8     int u;
     9     int v;
    10     int next;
    11 }edge[10001];
    12 int head[10001];
    13 int num=1;
    14 int rudu[1001];
    15 stack<int>s;
    16 int money[10001];
    17 int ans=0;
    18 int main()
    19 {
    20     int n,m;
    21     scanf("%d%d",&n,&m);
    22     for(int i=1;i<=n;i  )money[i]=100;
    23     for(int i=1;i<=n;i  )head[i]=-1;
    24     for(int i=1;i<=m;i  )
    25     {
    26         scanf("%d%d",&edge[num].v,&edge[num].u);
    27         edge[num].next=head[edge[num].u];
    28         rudu[edge[num].v]  ;
    29         head[edge[num].u]=num  ;
    30     }
    31     int tot=0;
    32     for(int i=1;i<=n;i  )
    33     {
    34         if(rudu[i]==0)
    35         {
    36             s.push(i);
    37             tot  ;
    38         }
    39     }
    40     
    41     while(s.size()!=0)
    42     {
    43         int p=s.top();
    44         s.pop();
    45         for(int i=head[p];i!=-1;i=edge[i].next)
    46         {
    47             if(money[edge[i].v]<money[edge[i].u] 1)
    48             money[edge[i].v]=money[edge[i].u] 1;
    49             rudu[edge[i].v]--;
    50             if(rudu[edge[i].v]==0)
    51             {
    52                 s.push(edge[i].v);
    53                 tot  ;
    54             }
    55         }
    56     }
    57     if(tot!=n)printf("-1");
    58     else 
    59     {
    60         for(int i=1;i<=n;i  )
    61         ans=ans money[i];
    62         printf("%d",ans);
    63     }
    64     return 0;
    65 }
    

     

    【难点陈述】 由于无敌的凡凡在二〇〇七年世界英俊秀气男总决选中胜出,Yali Company总老总Mr.Z心思好,决定给每位职工发奖金。...

    本文由威尼斯官方网站发布于威尼斯正规官网,转载请注明出处:不然输出叁个数表示最少总奖金

    关键词:

上一篇:Array是java中的数组

下一篇:没有了