首页 > 代码库 > hdu4185二分图匹配
hdu4185二分图匹配
Thanks to a certain "green" resources company, there is a new profitable industry of oil skimming. There are large slicks of crude oil floating in the Gulf of Mexico just waiting to be scooped up by enterprising oil barons. One such oil baron has a special plane that can skim the surface of the water collecting oil on the water‘s surface. However, each scoop covers a 10m by 20m rectangle (going either east/west or north/south). It also requires that the rectangle be completely covered in oil, otherwise the product is contaminated by pure ocean water and thus unprofitable! Given a map of an oil slick, the oil baron would like you to compute the maximum number of scoops that may be extracted. The map is an NxN grid where each cell represents a 10m square of water, and each cell is marked as either being covered in oil or pure water.
InputThe input starts with an integer K (1 <= K <= 100) indicating the number of cases. Each case starts with an integer N (1 <= N <= 600) indicating the size of the square grid. Each of the following N lines contains N characters that represent the cells of a row in the grid. A character of ‘#‘ represents an oily cell, and a character of ‘.‘ represents a pure water cell.OutputFor each case, one line should be produced, formatted exactly as follows: "Case X: M" where X is the case number (starting from 1) and M is the maximum number of scoops of oil that may be extracted.Sample Input
1 6 ...... .##... .##... ....#. ....## ......
Sample Output
Case 1: 3
题意：给一张图，问最大的连续两个格子数目有多少
题解：建图太麻烦，实在没想到，看网上思路才a的，把整个图分成i+j%2是否=1两个；然后匹配匈牙利算法就行了
坑点：刚开始以为由于是从上到下，从左到右遍历的，不用算i-1，j-1的情况，才发现这样会少算几种情况。
#include<map> #include<set> #include<cmath> #include<queue> #include<stack> #include<vector> #include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define pi acos(-1) #define ll long long #define mod 1000000007 using namespace std; const int N=600+5,maxn=100000+5,inf=0x3f3f3f3f; int n,color[N],col,row; int u[N][N]; char ma[N][N]; bool used[N],ok[N][N]; bool match(int x) { for(int i=1;i<=row;i++) { if(!used[i]&&ok[x][i]) { used[i]=1; if(color[i]==0||match(color[i])) { color[i]=x; return 1; } } } return 0; } int solve() { int ans=0; memset(color,0,sizeof color); for(int i=1;i<=col;i++) { memset(used,0,sizeof used); ans+=match(i); } return ans; } int main() { ios::sync_with_stdio(false); cin.tie(0); int t; cin>>t; for(int k=1;k<=t;k++) { cin>>n; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>ma[i][j]; col=row=0; memset(u,0,sizeof u); memset(ok,0,sizeof ok); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if(ma[i][j]==‘#‘) { if((i+j)%2==0)u[i][j]=++col; if((i+j)%2==1)u[i][j]=++row; } } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if((i+j)%2==0&&ma[i][j]==‘#‘) { if(i+1<=n&&ma[i+1][j]==‘#‘)ok[u[i][j]][u[i+1][j]]=1; if(j+1<=n&&ma[i][j+1]==‘#‘)ok[u[i][j]][u[i][j+1]]=1; if(i-1>=1&&ma[i-1][j]==‘#‘)ok[u[i][j]][u[i-1][j]]=1; if(j-1>=1&&ma[i][j-1]==‘#‘)ok[u[i][j]][u[i][j-1]]=1; } if((i+j)%2==1&&ma[i][j]==‘#‘) { if(i+1<=n&&ma[i+1][j]==‘#‘)ok[u[i+1][j]][u[i][j]]=1; if(j+1<=n&&ma[i][j+1]==‘#‘)ok[u[i][j+1]][u[i][j]]=1; if(i-1>=1&&ma[i-1][j]==‘#‘)ok[u[i-1][j]][u[i][j]]=1; if(j-1>=1&&ma[i][j-1]==‘#‘)ok[u[i][j-1]][u[i][j]]=1; } } /* for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) cout<<u[i][j]; cout<<endl; } for(int i=1;i<=col;i++) { for(int j=1;j<=row;j++) cout<<ok[i][j]; cout<<endl; }*/ cout<<"Case "<<k<<": "<<solve()<<endl; } return 0; }
hdu4185二分图匹配
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。