本文主要是介绍QDUOJ 29 帅气的HYC与N皇后(最大独立集)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目地址：点击打开链接
思路：暴搜肯定是会T的，每个位置和他一步能到的八个地方存在互斥关系，所以可以看作一个棋盘中有许许多多的互斥关系，互斥关系的两个点不能同时有棋子，所以可以将
互斥关系作边，从而问题转换成了求最大独立集。（最大独立集 = 顶点数 - 最大匹配）
独立集：
在所有的顶点中选取一些顶点，这些顶点两两之间没有连线，这些点就叫独立集
最大独立集：
在所有的独立集中，顶点数最多的那个集合
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int maxn = 1e3+5;
int row, col, k, N, match[maxn], link[maxn][maxn];
int Next[8][2] = {2, 1, 2, -1, -2, 1, -2, -1, 1, 2, 1, -2, -1, 2, -1, -2};
bool vis[maxn], use[maxn][maxn];
vector<int> g[maxn];bool dfs(int x)
{for(int i = 0; i < g[x].size(); i++){int v = g[x][i];if(!vis[v]){vis[v] = 1;if(match[v]==-1 || dfs(match[v])){match[v] = x;return 1;}}}return 0;
}int Hungary()
{int res = 0;for(int i = 1; i <= row*col; i++){memset(vis, 0, sizeof(vis));res += dfs(i);}return res;
}int main(void)
{while(cin >> row >> col >> k){memset(use, 0, sizeof(use));memset(match, -1, sizeof(match));for(int i = 0; i < maxn; i++)g[i].clear();int bad = 0;while(k--){int x, y;scanf("%d%d", &x, &y);use[x][y] = 1;for(int i = 0; i < 8; i++){int tx = x+Next[i][0];int ty = y+Next[i][1];if(tx >= 1 && tx <= row && ty >= 1 && ty <= col && !use[tx][ty]){use[tx][ty] = 1;bad++;}}}for(int i = 1; i <= row; i++)for(int j = 1; j <= col; j++)if(!use[i][j]){for(int k = 0; k < 8; k++){int tx = i+Next[k][0];int ty = j+Next[k][1];if(tx >= 1 && tx <= row && ty >= 1 && ty <= col && !use[tx][ty])g[(i-1)*col+j].push_back((tx-1)*col+ty);}}int ans = Hungary()/2;printf("%d\n", row*col-ans-bad);}return 0;
}
帅气的HYC与N皇后
发布时间: 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 6 0
6
2 2 0
4
3 3 0
5
1 1 1 1 1
1
5 1 1 1 1
5
这篇关于QDUOJ 29 帅气的HYC与N皇后(最大独立集)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
