上海网站建设报价方案,wordpress本地环境搭建,服装设计网上自学课程,长沙网站开发推荐题目描述 Description给出一张n*n(n100)的国际象棋棋盘#xff0c;其中被删除了一些点#xff0c;问可以使用多少1*2的多米诺骨牌进行掩盖。 输入描述 Input Description第一行为n#xff0c;m#xff08;表示有m个删除的格子#xff09;第二行到m1行为x,y#xff0c… 题目描述 Description 给出一张n*n(n100)的国际象棋棋盘其中被删除了一些点问可以使用多少1*2的多米诺骨牌进行掩盖。 输入描述 Input Description 第一行为nm表示有m个删除的格子第二行到m1行为x,y分别表示删除格子所在的位置x为第x行y为第y列 输出描述 Output Description 一个数即最大覆盖格数 样例输入 Sample Input 8 0 样例输出 Sample Output 32 数据范围及提示 Data Size Hint 经典问题 /*
模板题
*/
#includeiostream
#includecstdio
#includestring
#includecstring
#includealgorithm
#includevector
#includestack
#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 x0,f1;char chgetchar();while(!(ch0ch9)){if(ch-)f-1;chgetchar();};while(ch0ch9){xx*10(ch-0);chgetchar();};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;ie[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;}}coutans;
}
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][j1]){ins((i-1)*nj,(i-1)*nj1);ins((i-1)*nj1,(i-1)*nj);}if(i n !vis[i1][j]){ins((i-1)*nj,i*nj);ins(i*nj,(i-1)*nj);}}}hun();return 0;
} 转载于:https://www.cnblogs.com/hyfer/p/6000909.html
