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

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            国内精品欧美久久精品| 精品免费久久久久久久| 久久久久无码中| 久久午夜无码鲁丝片秋霞| 久久久亚洲欧洲日产国码aⅴ| 国产精品视频久久| 久久午夜夜伦鲁鲁片免费无码影视| 久久九九精品99国产精品| 91久久福利国产成人精品| 久久精品中文无码资源站| 国产一区二区精品久久凹凸| 亚洲αv久久久噜噜噜噜噜| 99久久精品免费看国产| 亚洲精品乱码久久久久久蜜桃图片| 99久久国产免费福利| 午夜精品久久久久久毛片| 久久国产精品免费| 久久97精品久久久久久久不卡| 中文国产成人精品久久不卡| 久久夜色撩人精品国产| 国产精品美女久久久m| 亚洲综合伊人久久综合| 污污内射久久一区二区欧美日韩| 青青青国产精品国产精品久久久久| 亚洲AV无码一区东京热久久| 久久久亚洲裙底偷窥综合| 久久综合给合综合久久| AAA级久久久精品无码区| 国产精品一久久香蕉国产线看| 三级三级久久三级久久| 伊人久久五月天| 伊人伊成久久人综合网777| 欧美激情精品久久久久久久九九九 | 久久强奷乱码老熟女| 国产亚州精品女人久久久久久 | 伊人色综合久久天天人手人婷 | 一本色道久久88综合日韩精品| 久久精品国产一区二区三区不卡 | 亚洲国产精品综合久久网络| 国产无套内射久久久国产| 精品视频久久久久|