codeforces511div1_b Little C Loves 3 II （二分图匹配 打表 找规律）

题意

给出 n和m并且$1< n,m < 1e9$1<n,m<1e9的矩阵，每次往里面放两个棋子，这两个棋子要满足曼哈顿距离等于3，问最多可以放多少枚棋子。

题解

你会发现手画是根本搞不出来的，想靠手画找规律可能需要有成为锦鲤的运气。每个点都可能会与周围距离为3的点配对，从而放下棋子，但当你在另一个位置放棋子时，若其周围距离为3的点与之前放棋子的点冲突，那该如何解决？ 这个问题便是二分图最大匹配问题，我们把方格看成点构成一张图跑二分图匹配即可。但是！ 若n,m小于100还好说，此题的n,m是爆炸级别的，根本没法跑复杂度平方级别的算法，那就用刚刚写的程序打表找找规律吧。 这里又有一个很神奇的地方，当n和m为奇数的时候，输出$n*m-1$n∗m−1，当其中一个为偶数的时候，输出$n*m$n∗m，但是！当n和m小于20的时候，这种情况就不在符合。所以对n和m小于20的情况，跑二分图匹配，其余的按照规律输出即可。（奇技淫巧啊）

代码

#include <bits/stdc  .h>
using namespace std;
const int maxn = 2000;
const int dr[] = {3,2,1,0,-3,-2,-1,0, 2, 1, 0,-3,-2,-1};
const int dc[] = {0,1,2,3, 0, 1, 2,3,-1,-2,-3,0,-1,-2};
const int MAXN = 2000;
const int INF = 0x3f3f3f3f;
long long n,m;
int cnt;
int g[maxn][maxn];
typedef pair<int,int> pii;
map<pii,int> id;
int ID(pii p) {
	if(id.count(p)) return id[p];
	return id[p] =   cnt;
}
int Nx,Ny;
void build() {
	for(int i = 0; i < n;   i)
		for(int j = 0; j < m;   j) {
			for(int k = 0; k < 14;   k) {
				int ni = i dr[k], nj = j dc[k];
				if(ni < 0 || ni >= n || nj < 0 || nj >= m) continue;
				g[ID(pii(i,j))][ID(pii(ni,nj))] = 1;
				Ny  ;
			}
		}
}

bool flag;
int  Mx[MAXN], My[MAXN];
int dx[MAXN], dy[MAXN], dis;
bool vst[MAXN];
bool searchP(void)
{
    queue <int> Q;
    dis = INF;
    memset(dx, -1, sizeof(dx));
    memset(dy, -1, sizeof(dy));
    for (int i = 1; i <= Nx; i  )
    if (Mx[i] == -1){
       Q.push(i); dx[i] = 0;
    }
    while (!Q.empty()) {
        int u = Q.front(); Q.pop();
        if (dx[u] > dis) break;
           for (int v = 1; v <= Ny; v  )
               if (g[u][v] && dy[v] == -1) {
                  dy[v] = dx[u] 1;
                if (My[v] == -1) dis = dy[v];
                else{
                     dx[My[v]] = dy[v] 1;
                     Q.push(My[v]);
                     }
                }
    }
    return dis != INF;
}

bool DFS(int u){

    for (int v = 1; v <= Ny; v  )
    if (!vst[v] && g[u][v] && dy[v] == dx[u] 1) {
       vst[v] = 1;
       if (My[v] != -1 && dy[v] == dis) continue;
       if (My[v] == -1 || DFS(My[v])) {
       My[v] = u; Mx[u] = v;
       return 1;
       }
    }
 return 0;
}

int MaxMatch(void){
    int res = 0;
    memset(Mx, -1, sizeof(Mx));
    memset(My, -1, sizeof(My));
    while (searchP()) {
          memset(vst, 0, sizeof(vst));
          for (int i = 1; i <= Nx; i  )
              if (Mx[i] == -1 && DFS(i)) res  ;
    }
    return res;
}
void init() {
	memset(g,0,sizeof g);
	id.clear();
	memset(vst, 0 ,sizeof vst);
	   memset(dx, -1, sizeof(dx));
    memset(dy, -1, sizeof(dy));
       memset(Mx, -1, sizeof(Mx));
    memset(My, -1, sizeof(My));
    cnt = 0;
}
/*
int main() {
	while(cin >> n >> m){
		init();
		Nx = n*m;
		Ny = 0;
		build();
		cout << MaxMatch() << endl;
	}
	return 0;
}

#include <bits/stdc  .h>
using namespace std;
*/

int main() {
	cin >> n >> m;
	if(n <= 20 && m <= 20) {
		Nx = n*m;
		Ny = 0;
		build();
		cout << MaxMatch() << endl;
	}
	else {
		if(n%2 == 0 && m%2 == 0)
			cout << n*m << endl;
		else if(n%2 == 0 && m%2 || n%2 && m%2==0)
			cout << n*m << endl;
		else {
			cout << n*m-1 << endl;
		}
	}
	return 0;
}

来源：http://www./content-4-56001.html