• <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不開心。。。。想想干這行,真不容易。。。尤其是在這個雞不生蛋,鳥不拉屎的地方。。。。。
            有句話怎么說的,太陽?。。?!
            不管怎么說,自己還是要好好學習真正有用的東西。。。。。
            我已經落下許多。。。。。。。。。
            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
            這個點提示一會是爆棧一會是超時,就算用了您說的奇偶性不同也無濟于事。。。  回復  更多評論
              
            <2009年3月>
            22232425262728
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            常用鏈接

            留言簿(8)

            隨筆檔案

            文章檔案

            Friends

            OJ

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            国内精品伊人久久久久影院对白| 亚洲国产精品无码久久九九| 97久久国产亚洲精品超碰热 | 思思久久精品在热线热| 久久久噜噜噜久久中文福利| 99久久国产主播综合精品 | 久久久久久久精品妇女99| AAA级久久久精品无码片| 色悠久久久久久久综合网| 亚洲AV无码久久精品狠狠爱浪潮| 91久久香蕉国产熟女线看| 2020久久精品亚洲热综合一本| 久久精品国产91久久麻豆自制| 区亚洲欧美一级久久精品亚洲精品成人网久久久久 | 精品人妻久久久久久888| 日本精品一区二区久久久| 国产美女久久久| 人妻无码αv中文字幕久久| 亚洲精品国精品久久99热| 99久久精品免费看国产| 久久精品中文字幕无码绿巨人| 色综合久久中文字幕综合网| 中文字幕亚洲综合久久2| 久久亚洲精品人成综合网| 久久亚洲中文字幕精品一区| 久久久久99精品成人片三人毛片| 国产亚洲精品自在久久| 久久WWW免费人成一看片| 伊人久久无码精品中文字幕| 久久国产精品一区| 国产精品伦理久久久久久 | 武侠古典久久婷婷狼人伊人| 久久93精品国产91久久综合| 久久香蕉一级毛片| 丁香久久婷婷国产午夜视频| 91精品国产综合久久四虎久久无码一级 | 亚洲精品国产综合久久一线| 久久久亚洲精品蜜桃臀| 精品久久久无码中文字幕天天| 日本免费久久久久久久网站| 国内精品久久久久国产盗摄|