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 阅读(341)
评论(2) 编辑 收藏 引用