找回密码
 立即注册
  • QQ空间
  • 回复
  • 收藏

算法 | 最大流算法求解含障碍物的国际棋盘中马(Knight)的最大数

admin 2019-5-17 06:39 330人围观 C++相关

问题描述

Description


Given a N×N chessboard. There are M obstacles in the chessboard and the position of i-th obstacle is (Xi,Yi). You are asked to find the maximum number of knights which can be placed in the chessboard at the same time, satisfied that,

  1. No two knights can attack each other.

  2. Knights can't be placed in obstacle.

  3. There can be at most one knight in a grid.

(A Knight in chess can attack 8 positions, as shown in following figure)



Input


Input is given from Standard Input in the following format:

N    M

X1   Y1

X2   Y2



XM   YM

Output


Print the maximum number of knights.

Sample Input 1

    3 21 13 3

    Sample Output 1

      5

      问题分析

      图的建立


      考虑格子的横纵坐标(x,y)之和:马每跳一次,其奇偶性必定改变,即给棋盘黑白染色后,马每次跳跃的起点和终点格子颜色一定是不同的. 于是考虑按照如下方法建图:

      将没有障碍物的格子视为结点,若马可以从格子a跳到格子b,则a,b之间存在一条双向边. 现将所有黑格(x+y为偶数)视为一个集合X,所有白格(x+y为奇数)视为一个集合Y,则所有的跳跃都发生在X,Y之间,而不会发生在X,Y的内部,于是该图为一个二分图.

      马的走法


      国际象棋中并没有“蹩马腿”一说,因此可以利用简单的坐标变换来表示马的移动:
        constint dx[] = {1, -1, 1, -1, 2, -2, 2, -2};const int dy[] = {-2, 2, 2, -2, 1, -1, -1, 1};

        图的算法


        问题所求为“最多能放多少个马”,即所建立图的最大独立集大小. 事实上,对于二分图我们有

        ∣最大独立集∣=总点数−最大匹配数

        所以只需求其最大匹配,一般来说有

        1. 利用匈牙利算法直接求解;

        2. 利用最大流求解

        两种方法.

        最大流Dinic算法


        1. X左侧增加一个源点S,向X中每一点都连入容量为1的边;

        2. Y右侧增加一个汇点T,Y中每一点都向其连入容量为1的边;

        3. X,Y 之间的边容量也为1;

        4. 跑一遍dinic,结果即为最大匹配.


        详细请参考:

        www.cnblogs.com/SYCstudio/p/7260613.html

        实现代码(内含注释)

          #include <bits/stdc++.h>using namespace std;
          constint maxn = 205; // Vertexconstint maxm = 1e6; // Edgeconstint inf = 0x7f7f7f7f; // Infinity
          // 定义马的一步移动constint dx[] = {1, -1, 1, -1, 2, -2, 2, -2};constint dy[] = {-2, 2, 2, -2, 1, -1, -1, 1};
          bool obstacle[maxn][maxn];
          // 以下为最大流Dinic算法模版
          int n, m, tot, Source, Dest;int dist[maxm], head[maxm];

          struct Edge{int to, nxt, capa; Edge() {} Edge(int a, int b, int c): to(a), nxt(b), capa(c) {}} e[maxm];

          void addedge(int u, int v, int capa) { e[tot] = Edge(v, head[u], capa); head[u] = tot++; e[tot] = Edge(u, head[v], 0); head[v] = tot++;}
          bool bfs() { memset(dist, -1, sizeof(dist)); std::queue<int> Q; Q.push(Source); dist[Source] = 0;while (!Q.empty()) {int x = Q.front(); Q.pop();for (int i = head[x]; i != -1; i = e[i].nxt) {int y = e[i].to;if (e[i].capa && dist[y] == -1) { dist[y] = dist[x] + 1; Q.push(y);if (y == Dest)returntrue; } } }returnfalse;}
          int dfs(int x, int exp) {if (x == Dest || !exp)return exp;int ret(0), tmp;for (int i = head[x]; i != -1; i = e[i].nxt) {int y = e[i].to;if (dist[x] + 1 == dist[y] && e[i].capa) { ret += (tmp = dfs(y, min(exp - ret, e[i].capa))); e[i].capa -= tmp; e[i ^ 1].capa += tmp; } }if (!ret) dist[x] = -1;return ret;}
          int dinic(){int ret(0);while (bfs()) ret += dfs(Source, inf); return ret;}
          // 以上为最大流Dinic算法模版
          // 初始化void init(int s, int t) { Source = s; Dest = t; memset(head, -1, sizeof(head));}
          // 判断(x,y)格子是否可以放马bool judge(int x, int y) {// x不能越界if (x < 1 || x > n) {returnfalse; }// y不能越界if (y < 1 || y > n) {returnfalse; }// (x,y)格子不能有障碍物return !obstacle[x][y];}
          // 二维坐标(x,y)化为一维int f(int x, int y) {return (x - 1) * n + y;}
          int main() {// 输入边长N和障碍物个数M cin >> n >> m;// 输入障碍物坐标for (int i = 0; i < m; i++) {int x, y; cin >> x >> y; obstacle[x][y] = true; } init(0, n * n + 1);for (int x = 1; x <= n; x++) {for (int y = 1; y <= n; y++) {if (obstacle[x][y]) continue;if ((x + y) & 1) { // x+y为奇数 addedge(Source, f(x, y), 1);for (int k = 0; k < 8; k++) {int xx = x + dx[k];int yy = y + dy[k];if (judge(xx, yy)) { addedge(f(x, y), f(xx, yy), 1); } } }else { addedge(f(x, y), Dest, 1); } } } cout << n * n - m - dinic() << endl;return0;}

          ----------------------------------------------------------------------------------------------------------------------
          我们尊重原创,也注重分享,文章来源于微信公众号:MEPHESTO,建议关注公众号查看原文。如若侵权请联系qter@qter.org。
          ----------------------------------------------------------------------------------------------------------------------

          鲜花

          握手

          雷人

          路过

          鸡蛋

          yafeilinux和他的朋友们微信公众号二维码

          微信公众号

          专注于Qt嵌入式Linux开发等。扫一扫立即关注。

          Qt开源社区官方QQ群二维码

          QQ交流群

          欢迎加入QQ群大家庭,一起讨论学习!

          我有话说......