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 閱讀(355)
評論(2) 編輯 收藏 引用