TouchStone
  Please Login
ログイン 登録
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P1506
  • 問題
  • P1506比武定工资
    制限 : 時間制限 : 10000 MS   メモリ制限 : 565536 KB
    問題説明

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

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

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

    入力形式

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

    出力形式

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

    サンプル入力 1

    7 4
    1 2
    3 4
    5 1
    3 4

    サンプル出力 1

    704

    サンプル入力 2

    7 10
    5 3
    7 4
    4 3
    7 6
    1 2
    4 3
    5 2
    5 6
    3 6
    2 3

    サンプル出力 2

    714

    ヒント

    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