网上做家教的网站,电气网站建设,wordpress 增加相册,卡尺 东莞网站建设正题 大意
求在一个扣掉m个格子的n*n的棋盘能放置的最多的马。 解题思路
求最大独立集就好了#xff0c;最大独立集点数-最大匹配数。最重要的是如何建图。定义一个数组point[i][j]表示点的编号。但是如果这样的话就会O(n4)O(n4)就会超时。现在我们把棋盘从左到右后从上到…正题 大意
求在一个扣掉m个格子的n*n的棋盘能放置的最多的马。 解题思路
求最大独立集就好了最大独立集点数-最大匹配数。最重要的是如何建图。定义一个数组point[i][j]表示点的编号。但是如果这样的话就会O(n4)O(n4)O(n^4)就会超时。现在我们把棋盘从左到右后从上到下标号那这样奇数就攻击不到奇数偶数就攻击不到偶数然后分两边构图就可以O(n4/2)O(n4/2)O(n^4/2)。 代码
#includecstdio
#includecstring
using namespace std;
int one,two,n,m,link[20001],ddx,ddy,w,s,zx[20001],zy[20001],point[201][201];
int tot,dx[8]{1,1,-1,-1,2,2,-2,-2},dy[8]{2,-2,2,-2,1,-1,1,-1};
bool a[201][201],cover[20001];
bool find(int i)//求最大匹配
{int k0;for (int j0;j8;j){if (zx[i]dx[j]1 || zy[i]dy[j]1 || zx[i]dx[j]n || zy[i]dy[j]n) continue;kpoint[zx[i]dx[j]][zy[i]dy[j]];//记录if (!a[zx[i]dx[j]][zy[i]dy[j]] !cover[k]){int qlink[k];link[k]i;cover[k]true;if (!q || find(q)) return true;link[k]q;}}return false;
}
int main()
{scanf(%d%d,n,m);for (int i1;im;i){ scanf(%d%d,ddx,ddy);a[ddx][ddy]true;}for (int i1;in;i)for (int j1;jn;j){if (!a[i][j]){if ((ij)%20) point[i][j]two;//标号else {point[i][j]one;//标号zx[one]i;//记录坐标zy[one]j;}}}s0;for (int i1;ione;i){memset(cover,0,sizeof(cover));if (find(i)) s;//找最大匹配数}printf(%d,n*n-m-s);
}
