首页 > 代码库 > hdu1507最大匹配

hdu1507最大匹配

2024-07-26 23:39:52   220人阅读

题意：给出n*m的矩阵方块，某些方块是ponds，这些方块不能出售，然后能出售的是1*2的方块

 要求求出有多少块1*2的方块能够出售，并输出这些方块的坐标（specia judge）

 

关键是怎么建出二分图，然后找最大匹配

可以把i+j==奇数的点提取出来，成为X集合，那么与（i，j）相邻的点就是Y集合了，然后就是二分图最大匹配

 1 //关键在于建图 2 #include <stdio.h> 3 #include <string.h> 4 #include <vector> 5 using namespace std; 6 const int N = 10000+10; 7 int Map[111][111]; 8 int n,m,k; 9 vector<int> G[N];10 int dx[] = {0,0,-1,1};11 int dy[] = {-1,1,0,0};12 bool vis[N];13 int cy[N];14 int cx[N];15 bool dfs(int u)16 {17     for(int i=0; i<G[u].size(); ++i)18     {19         int v = G[u][i];20         if(!vis[v])21         {22             vis[v] = true;23             if(cy[v] == -1 || dfs(cy[v]))24             {25                 cy[v] = u;26                 cx[u] = v;27                 return true;28             }29         }30     }31     return false;32 }33 int MaxMatch()34 {35     memset(cy, -1, sizeof(cy));36     memset(cx, -1, sizeof(cx));37     int t = m * n;38     int cnt = 0;39     for(int i=0; i<t; ++i)40     {41         if(cx[i] == -1)42         {43             memset(vis,0,sizeof(vis));44             cnt += dfs(i);45         }46     }47     return cnt;48 }49 int main()50 {51     int i,j,x,y;52     while(true)53     {54         scanf("%d%d",&n,&m);55         if(n==0 && m==0)56             break;57         scanf("%d",&k);58         for(i=0; i<N; ++i)59             G[i].clear();60         memset(Map, 0, sizeof(Map));61         for(i=0; i<k; ++i)62         {63             scanf("%d%d",&x,&y);64             x-=1; y-=1;65             Map[x][y] = 1;66         }67         for(i=0; i<n; ++i)68             for(j=0; j<m; ++j)69             if(Map[i][j] == 0 && (i+j)&1==1)70             {71                 x = i * n + j;72                 for(k=0; k<4; ++k)73                 {74                     int a = dx[k] + i;75                     int b = dy[k] + j;76                     if(a>=0 && b>=0 && a<n && b<m && Map[a][b] == 0)77                     {78                         y = a * n + b;79                         G[x].push_back(y);80                     }    81                 }82             }83         int ans = MaxMatch();84         printf("%d\n",ans);85         int t = n * m;86         for(i=0; i<t; ++i)87             if(cx[i] != -1)88                 printf("(%d,%d)--(%d,%d)\n",i/n+1,i%n+1,cx[i]/n+1,cx[i]%n+1);89         90     }91     return 0;92 }

 

hdu1507最大匹配


联系
我们