• <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
            這個點提示一會是爆棧一會是超時,就算用了您說的奇偶性不同也無濟于事。。。  回復  更多評論
              
            <2011年8月>
            31123456
            78910111213
            14151617181920
            21222324252627
            28293031123
            45678910

            常用鏈接

            留言簿(8)

            隨筆檔案

            文章檔案

            Friends

            OJ

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            久久国产视屏| 手机看片久久高清国产日韩| 精品久久久久久无码专区不卡 | 99久久亚洲综合精品成人| jizzjizz国产精品久久| 久久久久国产| 无码人妻久久久一区二区三区| 色综合久久中文色婷婷| 中文字幕精品久久久久人妻| 久久99国产精品尤物| 免费精品久久久久久中文字幕 | 青青草国产精品久久| 色天使久久综合网天天| 久久国产高清字幕中文| 久久久久久久精品成人热色戒| 色综合久久中文色婷婷| 色8久久人人97超碰香蕉987| 亚洲午夜久久久| 国产免费久久久久久无码| 国产亚洲精品自在久久| 久久WWW免费人成一看片| 久久久久无码中| 国产免费久久精品99久久| 久久免费精品视频| 精品蜜臀久久久久99网站| 中文字幕无码精品亚洲资源网久久| 三级韩国一区久久二区综合 | 亚洲国产精品久久久久网站| 久久精品欧美日韩精品| 亚洲精品无码久久久久| 综合久久国产九一剧情麻豆| 国产69精品久久久久观看软件| 国产A级毛片久久久精品毛片| 国内精品伊人久久久久777| 久久久久99精品成人片| 久久夜色撩人精品国产小说| 国产午夜精品理论片久久| 狠狠狠色丁香婷婷综合久久五月 | 国产人久久人人人人爽| 99re久久精品国产首页2020| 9191精品国产免费久久|