题目描述 Description
给出一张n*n(n<=100)的国际象棋棋盘，其中被删除了一些点，问可以使用多少1*2的多米诺骨牌进行掩盖。
输入描述 Input Description
第一行为n，m（表示有m个删除的格子）
第二行到m+1行为x,y，分别表示删除格子所在的位置
x为第x行
y为第y列
输出描述 Output Description
一个数，即最大覆盖格数
样例输入 Sample Input
8 0
样例输出 Sample Output
32
数据范围及提示 Data Size & Hint
经典问题
/* 模板题 */ #include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<vector> #include<stack> #define ll long long using namespace std; const int N = 30500; struct edge{ int v; int nxt; }e[N*3]; int head[N],cnt; int n,m; bool vis[205][205]; int chk[N],mch[N]; int read(){ int x=0,f=1; char ch=getchar(); while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();}; while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}; return x*f; } void ins(int u,int v){ cnt++; e[cnt].v = v; e[cnt].nxt = head[u]; head[u] = cnt; } bool dfs(int u){ int to; for(int i = head[u];i;i=e[i].nxt){ to = e[i].v; if(!chk[to]){ chk[to] = true; if(mch[to] == -1 || dfs(mch[to])){ mch[to] = u; mch[u] = to; return true; } } } return false; } void hun(){ int ans = 0,lm = n*n; memset(mch,-1,sizeof(mch)); for(int i = 1;i <= lm;i++){ if(mch[i] == -1){ memset(chk,0,sizeof(chk)); if(dfs(i)) ++ans; } } cout<<ans; } int main(){ n = read(); m = read(); int x,y; for(int i = 1;i <= m;i++){ y = read(); x = read(); vis[y][x] = true; } for(int i = 1;i <= n;i++){ for(int j = 1;j <= n;j++){ if(vis[i][j]) continue; if(j < n && !vis[i][j+1]){ ins((i-1)*n+j,(i-1)*n+j+1); ins((i-1)*n+j+1,(i-1)*n+j); } if(i < n && !vis[i+1][j]){ ins((i-1)*n+j,i*n+j); ins(i*n+j,(i-1)*n+j); } } } hun(); return 0; }