佛山网站建设有限公司,找别人做网站要注意什么,网络推广运营是什么,学做分类网站问题#xff1a;
n * m的矩阵#xff0c;有一些障碍点#xff0c;用12的骨牌覆盖所有非障碍点 (12骨牌可重叠#xff0c;骨牌可越界#xff0c;骨牌可延伸到障碍点) 问最少需要 多少个。
题解#xff1a; • 尽量用一个骨牌覆盖两个格子#xff0c;覆盖不了了再重叠使…问题
n * m的矩阵有一些障碍点用12的骨牌覆盖所有非障碍点 (12骨牌可重叠骨牌可越界骨牌可延伸到障碍点) 问最少需要 多少个。
题解 • 尽量用一个骨牌覆盖两个格子覆盖不了了再重叠使用骨牌 • 用和上一个题一样的方式求一个最大匹配那么就有2 * 最大匹配个点已经被覆盖了 • 剩下了总格子数-2 * 最大匹配个点每个点都需要一个骨牌 • 所以需要总格子数-2 * 最大匹配最大匹配 总格子-最大匹配个骨牌 • 一个结论 • 最小路径覆盖 选最少的边覆盖掉所有的点 总顶点数-最大匹配数 目前代码wa但是还没找到哪里错了基本思路是对的
代码
#includeiostream
#includecstring
using namespace std;const int maxn800;
int a[maxn][maxn];
int n,m;
int vis[maxn];
int link[maxn];
int lx,ly;
char c[maxn][maxn];
int maxmatch(int x)
{for(int i1;in*m;i){ //if((ij)%21){// if(i%21)continue;int yi;if(!a[x][y]||vis[y])continue;vis[y]1;if(link[y]0||maxmatch(link[y])){link[y]x;return 1;}}}return 0;
}
int main()
{int t;cint;while(t--){cinnm;memset(link,0,sizeof(link));memset(a,0,sizeof(a));memset(c,0,sizeof(c));char chgetchar();int tot0;for(int i1;in;i){for(int j1;jm;j){cinc[i][j];}char chgetchar();}for(int i1;in;i){for(int j1;jm;j){if(c[i][j]*){if(c[i-1][j]*)a[(i-2)*mj][(i-1)*mj]a[(i-1)*mj][(i-2)*mj]1;if(c[i1][j]*)a[(i)*mj][(i-1)*mj]a[(i-1)*jj][(i)*mj]1;if(c[i][j-1]*)a[(i-1)*mj-1][(i-1)*mj]a[(i-1)*jj][(i-1)*mj-1]1;if(c[i][j1]*)a[(i-1)*mj1][(i-1)*mj]a[(i-1)*jj][(i-1)*mj1]1;tot;}}} int sum0;for(int i1;in;i){for(int j1;jm;j){int x(i-1)*mj;if((ij)%20c[i][j]*){memset(vis,0,sizeof(vis));summaxmatch(x);}// if(i%20)continue;}}// printf(tot%d\n,tot);// printf(sum%d\n,sum);printf(%d\n,tot-sum);}return 0;
}
