P3425 [POI2005]KOS-Dicing

    • 20通过
    • 80提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 最小割 生成树 网络流 POI 2005 Special Judge 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB


  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示


    Dicing is a two-player game and its outcome is fully random. Lately its popularity increases all over Byteotia. There is even a special club for dicing amateurs in the capital city of Byteotia. The club patrons take their time talking to each other and playing their favourite game with a randomly chosen opponent every once in a while. Everyone who wins the most games one day gains the title of the lucky chap. Sometimes it happens that the night at the club is a quiet one and only few games are played. It is a time when even one win can make you a lucky chap.

    Once upon a time a most unlucky fellow, Byteasar, won the glorious title. He was so deeply shocked that he completely forgot how many games he had won. Now he is wondering how good his luck was and whether fortune finally smiled upon him - perhaps his luck changed for good? He knows exactly how many games and between whom were played that lucky night. However, he does not know the results. Byteasar desires to find out what is the smallest number of wins that could provide the title of the lucky chap. Be a good fellow and help him satisfy his curiosity!

    TaskWrite a programme that:

    for each game played reads from the standard input the pair of players who competed in it.

    finds the smallest number $k$ , such that a set of games' outcomes exists in which each player wins $k$ games at the most,writes the number $k$ and the results of games in the found set to the standard output.

    Dicing 是一个两人玩的游戏,这个游戏在Byteotia非常流行. 甚至人们专门成立了这个游戏的一个俱乐部. 俱乐部的人时常在一起玩这个游戏然后评选出玩得最好的人.现在有一个非常不走运的家伙,他想成为那个玩的最好的人,他现在知道了所有比赛的安排,他想知道,在最好的情况下,他最少只需要赢几场就可以赢得冠军,即他想知道比赛以后赢的最多的那个家伙最少会赢多少场.



    In the first line of the standard input there is a pair of integers $n$ and $m$ separated by a single space, $1\le n\le 10000$ , $0\le m\le 10000$ ; $n$ denotes the number of players, while $m$ is the number of games. The players are numbered from $1$ to $n$ . In the following $m$ lines there are pairs of players' numbers depicting the sequence of games, separated by single spaces. One pair may occur many times in the sequence.


    The first line of the standard output should contain the determined number $k$ . For each pair of players' numbers $a$ , $b$ specified in the $i$ 'th line of the input, in the $i$ 'th line of the output the number $1$ should be written if the player no. $a$ wins against player no. $b$ in the found set of outcomes, or $0$ otherwise.


    输入样例#1: 复制
    4 4
    1 2
    1 3
    1 4
    1 2
    输出样例#1: 复制