• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            posts - 74,  comments - 33,  trackbacks - 0
            Knights

            Time limit: 10sec. Submitted: 167
            Memory limit: 32M Accepted: 58
            Source : BOI 2001

            We are given a chess-board of size n*n, from which some fields have been removed. The task is to determine the maximum number of knights that can be placed on the remaining fields of the board in such a way that none of them check each other.


            Fig.1: A knight placed on the field S checks fields marked with x.

            Task

            Write a program, that:

            • reads the description of a chess-board with some fields removed
            • determines the maximum number of knights that can be placed on the chess-board in such a way that none of them check each other,

            Input

            The first line of the input file contains two integers n and m, separated by a single space, 1<=n<=200, 0<=m<n2; n is the chess-board size and m is the number of removed fields. Each of the following m lines contains two integers: x and y, separated by a single space, 1<=x,y<=n -- these are the coordinates of the removed fields. The coordinates of the upper left corner of the board are (1,1), and of the bottom right are (n,n). The removed fields are not repeated in the file.

            There are multiple test cases. Process to end of file.

            Output

            The output should contain one integer (in the first and only line of the file). It should be the maximum number of knights that can be placed on the given chess-board without checking each other.

            Sample Input

            3 2
            1 1
            3 3
            

            Sample output

            5
            怎么說呢,這道題。。。。。
            很無語。。。。開始的時候我一直從x,y奇偶相同的的點尋找匹配,結果就TLE了N次。我很無語。。。。。
            我想我的匹配也是鄰接表的。。。。為什么那么多AC的而我吧卻是TLE呢,我抱著試試看的想法改成從奇偶性不同的點
            開始尋找匹配,結果AC。。。。。我無語。。。。不知道該如何是好。。。。。。。
            二分最大匹配代碼如下:
            int?H(int?t)?{?
            ????
            int?i;?
            ????
            for(i=0;i<v[t].size();i++)?{?
            ???????
            if(flag[v[t][i]]==0)?{?
            ???????????flag[v[t][i]]
            =1;?
            ???????????
            if(pre[v[t][i]]==-1?||?H(pre[v[t][i]]))?{?
            ??????????????pre[v[t][i]]
            =t;?
            ??????????????
            return?1;?
            ???????????}
            ?
            ???????}
            ?
            ????}
            ?
            ????
            return?0;?
            }
            ?
            int?MaxMatch()?{?
            ????
            int?i,num;?
            ????memset(pre,
            0xff,sizeof(pre));?
            ????
            for(num=0,i=1;i<odd;i++){?
            ????????
            if(!v[i].size())continue;
            ???????????memset(flag,
            0,sizeof(flag));?
            ???????????
            if(H(i))num++;??
            ????}
            ?
            ????
            return?num;?
            }
            總之,最近就是TMD不開心。。。。想想干這行,真不容易。。。尤其是在這個雞不生蛋,鳥不拉屎的地方。。。。。
            有句話怎么說的,太陽啊?。。?br />不管怎么說,自己還是要好好學習真正有用的東西。。。。。
            我已經落下許多。。。。。。。。。
            Good Good study.......
            Day Day up........
            posted on 2009-03-12 20:09 KNIGHT 閱讀(346) 評論(2)  編輯 收藏 引用

            FeedBack:
            # re: Knights
            2011-08-23 21:53 | Lightning
            請問您說的奇偶性不同的x,y是指什么?  回復  更多評論
              
            # re: Knights
            2011-08-24 19:34 | Lightning
            我用PASCAL寫的程序倒數第二個點過不了
            200 4
            3 1
            3 2
            3 3
            2 3
            這個點提示一會是爆棧一會是超時,就算用了您說的奇偶性不同也無濟于事。。。  回復  更多評論
              
            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            常用鏈接

            留言簿(8)

            隨筆檔案

            文章檔案

            Friends

            OJ

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            欧洲精品久久久av无码电影| 中文字幕无码久久久| 久久久亚洲裙底偷窥综合| 亚洲欧美精品一区久久中文字幕| 欧美亚洲国产精品久久高清| 久久午夜伦鲁片免费无码| 国产成人久久精品区一区二区| 91精品国产91久久| 一本一本久久A久久综合精品 | 国产亚洲精品久久久久秋霞| 久久国产高清字幕中文| 中文字幕无码久久人妻| 久久久久久久99精品免费观看| 午夜视频久久久久一区 | 久久露脸国产精品| 久久精品无码专区免费青青| 久久综合九色综合欧美就去吻| 国产婷婷成人久久Av免费高清| 国产精品99久久不卡| 国内精品久久久久久久亚洲| 国产精品成人久久久| 久久96国产精品久久久| 久久精品国产亚洲AV无码麻豆| 久久精品成人免费国产片小草| 欧美精品九九99久久在观看| 狠狠色综合网站久久久久久久| 久久人人爽爽爽人久久久| 久久久久久国产a免费观看黄色大片| 久久久久久免费一区二区三区| 中文无码久久精品| 久久午夜无码鲁丝片秋霞| 久久影院亚洲一区| 三级片免费观看久久| 久久亚洲2019中文字幕| 一级做a爰片久久毛片人呢| 久久91综合国产91久久精品| 91精品国产色综合久久| 香蕉久久一区二区不卡无毒影院| 国产精品久久久久久久久鸭| 亚洲国产成人久久综合碰碰动漫3d| 99久久免费国产特黄|