标题来源：
意甲冠军：假设a[i][j] ！= -1 把他转成二进制 最多有12位 代表题目那张图的12个位置 假设相应位是1 说明在那里放一个守卫能够看住a[i][j]位置上的这个东西
思路：明显死最小点覆盖 奇偶匹配建图
#include#include #include using namespace std;const int maxn = 55;int vis[maxn*maxn];int y[maxn*maxn];vector G[maxn*maxn];int n, m;int a[maxn][maxn];int dir[12][2] = {-1, -2, -2, -1, -2, 1, -1, 2, 1, 2, 2, 1, 2, -1, 1, -2, -1, 0, 0, 1, 1, 0, 0, -1};bool dfs(int u){ for(int i = 0; i < G[u].size(); i++) { int v = G[u][i]; if(vis[v]) continue; vis[v] = true; if(y[v] == -1 || dfs(y[v])) { y[v] = u; return true; } } return false;}int match(){ int ans = 0; memset(y, -1, sizeof(y)); for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { if((i+j)%2) { memset(vis, 0, sizeof(vis)); if(dfs(i*m+j)) ans++; } } } return ans;}int main(){ int cas = 1; while(scanf("%d %d", &n, &m) && (n||m)) { for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) scanf("%d", &a[i][j]); for(int i = 0; i < n*m; i++) G[i].clear(); for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { int x = a[i][j]; if(x == -1) continue; for(int k = 0; k < 12; k++, x >>= 1) { if(!x) break; if(!(x&1)) continue; int xx = i + dir[k][0]; int yy = j + dir[k][1]; if(xx < 0 || xx >= n || yy < 0 || yy >= m) continue; if(a[xx][yy] == -1) continue; if((i+j)%2) G[i*m+j].push_back(xx*m+yy); else G[xx*m+yy].push_back(i*m+j); } } } printf("%d. %d\n", cas++, match()); } return 0;}
版权声明：本文博客原创文章。博客，未经同意，不得转载。