发布时间: 2015年11月1日 16:34 最后更新: 2015年11月1日 16:35 时间限制: 5000ms 内存限制: 512M
描述你一定听说过N皇后问题吧。
但是帅气的HYC已经开始厌倦这古老的题目了。所以他设计了新的问题——N骑士问题。
这个问题跟N皇后很类似，同样是在国际象棋的棋盘上，只是把皇后(Queen)换成了 骑士(Knight ♞），就相当于中国象棋里的马了（所以说还是叫马好了～），不过要特别注意的一点是，国际象棋里的马是不会被绊马腿的（如果你不知道我在说什么，请忽略这句，并看下一段，这并不影响你解决这个问题）。
HYC会给出一个n行m列棋盘，你需要往棋盘上尽量放置更多的Knight，并保证他们无法相互攻击。
下图展示了国际象棋中马（Knight）的攻击范围：
（黑色的马可以攻击它周围任何一个黑点表示的位置，而白色的马可以攻击任意白点标示的位置）
而且为了增加难度，HYC会提前在棋盘上随意放置k个马（保证预先放置的马无法互相攻击）
你要计算并输出最终棋盘上可以共存的马的个数（也包含预先放置的个数）
输入每次测试仅有一组数据，第一行包含三个正整数（用空格隔开） n m k分别表示棋盘的行数和列数，k表示预先放置的马的数量。接下来k行每行包含两个正整数xi， yi表示这x个棋子放在第xi行yi列（xi, yi从1开始编号，见题目描述中的图片上标示的坐标） 数据范围： m,n,k,xi,yi均为正整数。m， n均不大于60 且 n×m不大于2^6，k不大于60， xi<=n, yi<=m
输出只有一行，一个整数按照上边的规则棋盘上最多可以放置的马的个数
样例输入1 复制 1 6 0 样例输出1 6 样例输入2 复制 2 2 0 样例输出2 4 样例输入3 复制 3 3 0 样例输出3 5 样例输入4 复制 1 1 1 1 1 样例输出4 1 样例输入5 复制 5 1 1 1 1 样例输出5 5思路：每个位置和他一步能到的八个地方存在互斥关系，所以可以看作一个棋盘中有许许多多的互斥关系，互斥关系的两个点不能同时有棋子，所以可以将互斥关系作边，从而问题转换成了求最大独立集， 注意本来就放上的棋子，他周围的8个棋子就算是废了，不可以放棋子了，但是独立集会把单独的点算进去， 所以要减去这些点。
总结下：最大独立集问题， 通常是存在一些关系导致你在我不能在的局面， 然后让你求最优，这时候，我们就通过这些关系来建边，把所有存在这种关系的点都连起来，跑一边最大独立集，就是不存在关系都是好的点啦~
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> using namespace std; const int maxn = 100; int match[maxn*maxn*8], book[maxn*maxn*8], n, m, p, used[maxn][maxn]; int dir[8][2] = {2, 1, 2, -1, -2, 1, -2, -1, 1, 2, 1, -2, -1, 2, -1, -2}; vector<int> v[maxn]; int Find(int x) { for(int i = 0; i < v[x].size(); i++) { int to = v[x][i]; if(book[to]) continue; book[to] = 1; if(!match[to] || Find(match[to])) { match[to] = x; return 1; } } return 0; } int main() { while(~scanf("%d%d%d", &n, &m, &p)) { int bad = 0; memset(match, 0, sizeof(match)); memset(used, 0, sizeof(used)); for(int i = 0; i < maxn*maxn; i++) v[i].clear(); int ans = 0, x, y; for(int i = 1; i <= p; i++) { scanf("%d%d", &x, &y); used[x][y] = 1; for(int i = 0; i < 8; i++) { int tx = x + dir[i][0]; int ty = y + dir[i][1]; if(tx >= 1 && tx <= n && ty >= 1 && ty <= m && !used[tx][ty]) { used[tx][ty] = 1; bad++; } } } for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) if(!used[i][j]) { for(int k = 0; k < 8; k++) { int tx = i + dir[k][0]; int ty = j + dir[k][1]; if(tx >= 1 && tx <= n && ty >= 1 && ty <= m && !used[tx][ty]) v[(i-1)*m+j].push_back((tx-1)*m+ty); } } for(int i = 1; i <= n*m; i++) { memset(book, 0, sizeof(book)); ans += Find(i); } printf("%d\n", n*m-ans/2-bad); } return 0; }