POJ2446【建图建图】

题意：
给你一个n*n的矩阵，然后再给你几个坑，然后问你能否被1*2的长方形给覆盖；

• -弱知道了是二分匹配的做法，但是弱还是不会转化，又是在建图上GG了

分析：
从国际象棋的那个黑白色理解，这是一张二分图（好像非常有道理）

建图：由于是1*2的纸片覆盖，那么这个区域的两个点的（i+j）必然是一个奇数和一个偶数。
先搞好点，我们分别给奇数、偶数点 依次从1开始标号，相邻的就是有一条边；
这波建图好是经典；
一般建图弱感觉就是：先搞点，再建图，有些还会再初始化一波；

然后就是求一下最大匹配，
如果最大匹配+K=N*M就输出”YES”，否则就是”NO”

#include<iostream> #include<stdio.h> #include<string.h> #include<map> #include<stack> #include<algorithm> using namespace std; #define N 1500int ma[N][N]; int ls[N][N]; int n,m,t; int cx[N]; int cy[N]; int ji,ou; bool vis[N];int findpath(int u) {for(int i=1;i<ou;i++){if(!vis[i]&&ma[u][i]){vis[i]=1;if(cy[i]==-1||findpath(cy[i])){cx[u]=i;cy[i]=u;return 1;}}}return 0; }void solve() {memset(cx,-1,sizeof(cx));memset(cy,-1,sizeof(cy));int ans=0;for(int i=1;i<ji;i++){memset(vis,0,sizeof(vis));ans+=findpath(i);}ans*2==(m*n-t)?printf("YES\n"):printf("NO\n"); }int main() {while(~scanf("%d%d",&n,&m)){scanf("%d",&t);memset(ls,0,sizeof(ls));for(int i=0;i<t;i++){int x,y;scanf("%d%d",&x,&y);ls[y][x]=-1;}ji=ou=1;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(ls[i][j]!=-1){if((i+j)%2==0)ls[i][j]=ji++;elsels[i][j]=ou++;}}}memset(ma,0,sizeof(ma));for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(ls[i][j]!=-1&&(i+j)%2==1){if(ls[i-1][j]>=1)ma[ls[i-1][j]][ls[i][j]]=1;if(ls[i+1][j]>=1)ma[ls[i+1][j]][ls[i][j]]=1;if(ls[i][j-1]>=1)ma[ls[i][j-1]][ls[i][j]]=1;if(ls[i][j+1]>=1)ma[ls[i][j+1]][ls[i][j]]=1;}}}solve();}return 0; } [ls[i][j]]=1;}}}solve();}return 0; }

转载于:https://www.cnblogs.com/keyboarder-zsq/p/5934535.html

总结

以上是生活随笔为你收集整理的POJ2446【建图建图】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。