TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1506
  • 题目
  • P1506比武定工资
    限制 : 时间限制 : 10000 MS   空间限制 : 565536 KB
    问题描述

    由于粉丝众多,何老板出门经常遇到粉丝们的围堵,这让何老板很是烦恼。于是何老板雇佣了n个保镖。怎样给保镖们定工资,这成了个大问题,保镖们个个都号称武林高手,于是何老板决定按照功夫的高低来定工资。何老板问:你们中谁的功夫最厉害?
    “我!我会降龙十八掌!”
    “我!我练过《葵花宝典》!”
    “我!我会天马流星拳!”
    “我!我会神龟冲击波!”
    “我!我有钢铁侠套装!”
    “我!我爸是李刚!”
    ......

    保镖们吵得何老板头都要炸了,于是何老板决定,通过比武来决定工资的高低。何老板规定保镖的工资都是整数,最低工资是100元。若保镖x打赢了保镖y,那么x的工资应该比y的要高。对于这种方式,保镖们纷纷表示支持。

    于是比武开始了,总共进行了m场比武,何老板想根据比武结果,找出一种工资方案,使得总的工资数最少。

    输入格式

    第一行两个空格间隔的整数n,m,表示保镖的总数和比武的场数;
    接下来m行,每行两个空格间隔的整数x,y,表示这场比武x号保镖打赢了y号保镖。

    输出格式

    若不能找到合理的工资方案,则输出“no solution”;否则输出一个整数表示最少的工资数。

    样例输入

    7 4
    1 2
    3 4
    5 1
    3 4

    样例输出

    704

    提示

    5打赢1,1打赢2。2的工资是100,1的工资是101,5的工资是102
    3打赢4。4的工资是100,3的工资是101
    6和7没有参与比赛,拿最低工资100
    总计704


    80%的数据满足n<=1000,m<=2000;
    100%的数据满足n<=6000,m<=20000