題目描述?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; }
?
)
