• <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

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            精品久久久久久国产免费了| 无码人妻久久一区二区三区蜜桃 | 国产亚洲欧美成人久久片| 久久精品蜜芽亚洲国产AV| 欧美久久精品一级c片片| 久久综合色区| 91精品国产91久久综合| 亚洲欧美国产日韩综合久久| 午夜久久久久久禁播电影| 久久强奷乱码老熟女网站| 久久夜色精品国产噜噜亚洲AV| 国产精品日韩欧美久久综合| 精品熟女少妇AV免费久久| 亚洲精品高清久久| 无码人妻精品一区二区三区久久| 久久美女人爽女人爽| 亚洲伊人久久大香线蕉综合图片| 久久久精品视频免费观看| 狠狠干狠狠久久| 国产精品久久久久jk制服| 久久婷婷五月综合国产尤物app| 国产亚洲色婷婷久久99精品91| 久久香蕉超碰97国产精品| 亚洲香蕉网久久综合影视| 精品国产日韩久久亚洲| 久久久久久久综合日本亚洲| 久久婷婷五月综合97色| 亚洲国产精品无码久久一区二区| 香蕉aa三级久久毛片 | 久久精品国产亚洲av麻豆蜜芽| 久久精品国产WWW456C0M| 2020最新久久久视精品爱 | 国产真实乱对白精彩久久| 狠狠色丁香久久婷婷综合五月| 一本一本久久a久久综合精品蜜桃| 四虎国产精品成人免费久久| 日韩十八禁一区二区久久| 久久这里有精品| 日本久久久久亚洲中字幕| 色欲综合久久躁天天躁蜜桃| 日韩人妻无码精品久久久不卡 |