青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

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
怎么說(shuō)呢,這道題。。。。。
很無(wú)語(yǔ)。。。。開(kāi)始的時(shí)候我一直從x,y奇偶相同的的點(diǎn)尋找匹配,結(jié)果就TLE了N次。我很無(wú)語(yǔ)。。。。。
我想我的匹配也是鄰接表的。。。。為什么那么多AC的而我吧卻是TLE呢,我抱著試試看的想法改成從奇偶性不同的點(diǎn)
開(kāi)始尋找匹配,結(jié)果AC。。。。。我無(wú)語(yǔ)。。。。不知道該如何是好。。。。。。。
二分最大匹配代碼如下:
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不開(kāi)心。。。。想想干這行,真不容易。。。尤其是在這個(gè)雞不生蛋,鳥(niǎo)不拉屎的地方。。。。。
有句話怎么說(shuō)的,太陽(yáng)啊!!!
不管怎么說(shuō),自己還是要好好學(xué)習(xí)真正有用的東西。。。。。
我已經(jīng)落下許多。。。。。。。。。
Good Good study.......
Day Day up........
posted on 2009-03-12 20:09 KNIGHT 閱讀(357) 評(píng)論(2)  編輯 收藏 引用

FeedBack:
# re: Knights
2011-08-23 21:53 | Lightning
請(qǐng)問(wèn)您說(shuō)的奇偶性不同的x,y是指什么?  回復(fù)  更多評(píng)論
  
# re: Knights
2011-08-24 19:34 | Lightning
我用PASCAL寫(xiě)的程序倒數(shù)第二個(gè)點(diǎn)過(guò)不了
200 4
3 1
3 2
3 3
2 3
這個(gè)點(diǎn)提示一會(huì)是爆棧一會(huì)是超時(shí),就算用了您說(shuō)的奇偶性不同也無(wú)濟(jì)于事。。。  回復(fù)  更多評(píng)論
  

只有注冊(cè)用戶(hù)登錄后才能發(fā)表評(píng)論。
網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問(wèn)   Chat2DB   管理


<2011年8月>
31123456
78910111213
14151617181920
21222324252627
28293031123
45678910

常用鏈接

留言簿(8)

隨筆檔案

文章檔案

Friends

OJ

搜索

  •  

最新評(píng)論

閱讀排行榜

評(píng)論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            中文高清一区| 欧美一级专区| 亚洲国产成人精品女人久久久 | 国产精品乱看| 欧美亚洲一区二区三区| 午夜欧美大尺度福利影院在线看| 国产精品亚洲欧美| 久久久综合视频| 蜜臀久久99精品久久久久久9| 亚洲精品五月天| 一本色道久久综合狠狠躁篇怎么玩| 欧美系列电影免费观看| 久久精品人人做人人爽| 免费在线观看成人av| 亚洲午夜精品久久久久久浪潮| 亚洲综合好骚| 亚洲国产小视频| 一区二区久久| 一区二区三区在线免费观看| 亚洲国产精品成人久久综合一区 | 久久精品国产免费观看| 亚洲免费观看高清完整版在线观看| 夜久久久久久| 亚洲第一免费播放区| 亚洲少妇自拍| 亚洲国产精品久久久久秋霞蜜臀| 99国产精品久久久久久久成人热 | 国产欧美日韩精品专区| 欧美大片免费| 国产欧美精品| 亚洲日本电影在线| 黄色在线成人| 亚洲在线观看免费| 亚洲精品乱码久久久久| 午夜电影亚洲| 一区二区三区四区国产精品| 久久国产精品亚洲77777| 亚洲午夜电影在线观看| 久久亚洲综合色| 久久精品一区| 国产精品一区在线观看你懂的| 欧美激情视频一区二区三区不卡| 国产欧美日韩三级| 99精品热视频只有精品10| 亚洲欧洲日产国产网站| 午夜欧美大尺度福利影院在线看| 日韩午夜剧场| 免费久久99精品国产自| 久久天天综合| 激情一区二区三区| 欧美一级夜夜爽| 欧美资源在线| 国产啪精品视频| 亚洲欧美日韩一区二区三区在线观看 | 日韩系列欧美系列| 欧美jizzhd精品欧美巨大免费| 久久亚洲国产成人| 国产欧美日韩精品丝袜高跟鞋| 亚洲午夜成aⅴ人片| 亚洲一品av免费观看| 欧美日韩精品国产| 亚洲免费成人av电影| 一区二区三区视频在线观看 | 亚洲综合色丁香婷婷六月图片| 一本大道久久a久久综合婷婷| 欧美高清视频在线| 亚洲精品日韩激情在线电影 | 国产香蕉97碰碰久久人人| 亚洲欧美日本在线| 久久久久综合网| 黄色精品网站| 免费黄网站欧美| 亚洲乱码国产乱码精品精| 亚洲性视频网站| 国产精品一页| 久久网站热最新地址| 欧美激情视频在线播放| 亚洲精品久久久久久久久久久久久 | 欧美日韩精品一区二区在线播放| 91久久精品日日躁夜夜躁国产| 亚洲精品一区二区三区99| 欧美人成在线| 午夜精品一区二区三区在线播放 | 久久久激情视频| 亚洲高清不卡一区| 欧美日韩精品一区二区在线播放 | 免费观看日韩av| 亚洲乱码日产精品bd| 国产精品第一区| 久久精品成人| 91久久精品国产91久久性色| 亚洲在线网站| 激情自拍一区| 国产精品成人v| 久久资源在线| 亚洲一线二线三线久久久| 久久婷婷国产麻豆91天堂| 亚洲精品一线二线三线无人区| 国产精品久久久久一区二区三区共| 欧美一区二区在线播放| 亚洲国产精品成人一区二区| 午夜精品在线视频| 亚洲麻豆国产自偷在线| 国产精品一卡| 欧美日韩精品久久久| 久久精品国产精品亚洲综合 | 亚洲国产一区二区在线| 欧美一区二区三区免费视频| 亚洲激情视频网| 国产视频一区在线观看一区免费| 欧美大秀在线观看| 欧美一区二区三区在线| 日韩午夜在线| 亚洲国产中文字幕在线观看| 久久国产手机看片| 亚洲视频 欧洲视频| 亚洲国产日韩欧美在线动漫| 国产精自产拍久久久久久| 欧美日韩国产黄| 欧美成年人网| 久久综合久色欧美综合狠狠| 新片速递亚洲合集欧美合集| 日韩亚洲国产精品| 亚洲国产一二三| 久久青草欧美一区二区三区| 一区二区三区日韩精品视频| 欧美一级夜夜爽| 久久久精品视频成人| 久久九九精品| 亚洲国产第一| 麻豆av一区二区三区久久| 欧美亚洲免费电影| 亚洲综合社区| 亚洲在线网站| 午夜欧美不卡精品aaaaa| 亚洲一区二区伦理| 在线性视频日韩欧美| aa成人免费视频| 99精品99| 中文一区二区| 亚洲在线一区二区| 欧美在线视频在线播放完整版免费观看| 一区二区三区精品| 亚洲一二三区在线| 亚洲欧美日韩直播| 亚欧成人在线| 久久久久久91香蕉国产| 久久蜜桃av一区精品变态类天堂| 久久九九热免费视频| 久久综合婷婷| 亚洲国产欧美不卡在线观看| 亚洲国产精品成人精品| 亚洲精品欧美极品| 亚洲一卡二卡三卡四卡五卡| 亚洲中字黄色| 久久视频精品在线| 欧美精品在线观看播放| 国产精品久久久久9999| 国产精品综合色区在线观看| 国模精品一区二区三区| 亚洲激情中文1区| 亚洲私人黄色宅男| 久久国产精品电影| 欧美成熟视频| 亚洲天天影视| 久久久亚洲精品一区二区三区 | 国产精品人人做人人爽人人添| 国产欧美日韩视频在线观看 | 亚洲人成网站影音先锋播放| 亚洲视频第一页| 久久蜜桃精品| 亚洲激情在线| 久久av一区二区三区| 欧美不卡在线| 国产午夜精品视频| 亚洲三级视频在线观看| 午夜日本精品| 亚洲第一精品影视| 久久国产精品久久久| 日韩一级不卡| 亚洲电影毛片| 黄色小说综合网站| 9人人澡人人爽人人精品| 午夜精品av| 欧美国产日韩一区| 国产偷国产偷亚洲高清97cao| 亚洲第一免费播放区| 亚洲欧美精品在线观看| 欧美二区不卡| 亚洲图片你懂的| 欧美黑人一区二区三区| 国产一区清纯| 亚洲欧美网站| 亚洲片国产一区一级在线观看| 校园春色国产精品| 欧美亚洲不卡| 夜夜嗨av色一区二区不卡| 久久亚洲综合色| 午夜精品国产更新| 国产精品久久久久久妇女6080|