首页 > 代码库 > 4185 Oil Skimming 最大匹配 奇偶建图
4185 Oil Skimming 最大匹配 奇偶建图
题目大意：
统计相邻（上下左右）的‘#’的对数。
解法：
与题目hdu1507 Uncle Tom‘s Inherited Land*类似，需要用奇偶建图。就是行+列为奇数的作为X集合，偶尔作为Y集合，都是‘#’就连边。最后求最大匹配。
数据有点大，直接建图会出错（我试过）。可以按照‘#’出现的顺序给顶点编号。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<queue> 5 #include<vector> 6 #include<algorithm> 7 using namespace std; 8 const int N=36005,INF=0x3f3f3f3f; 9 int cx[N],cy[N],dx[N],dy[N]; 10 bool bmask[N]; 11 vector<int > bmap[N]; 12 int nx,ny,dis,ans; 13 bool searchpath() 14 { 15 queue<int> q; 16 dis=INF; 17 memset(dx,-1,sizeof(dx)); 18 memset(dy,-1,sizeof(dy)); 19 for(int i=1;i<=nx;i++) 20 { 21 if(cx[i]==-1){ q.push(i); dx[i]=0; } 22 while(!q.empty()) 23 { 24 int u=q.front(); q.pop(); 25 if(dx[u]>dis) break; 26 for(int i=0;i<bmap[u].size();i++) 27 { 28 int v=bmap[u][i]; 29 if(dy[v]==-1) 30 { 31 dy[v]= dx[u] + 1; 32 if(cy[v]==-1) dis=dy[v]; 33 else 34 { 35 dx[cy[v]]= dy[v]+1; 36 q.push(cy[v]); 37 } 38 } 39 } 40 } 41 } 42 return dis!=INF; 43 } 44 int findpath(int u) 45 { 46 for(int i=0;i<bmap[u].size();i++) 47 { 48 int v=bmap[u][i]; 49 if(!bmask[v]&&dy[v]==dx[u]+1) 50 { 51 bmask[v]=1; 52 if(cy[v]!=-1&&dy[v]==dis) continue; 53 if(cy[v]==-1||findpath(cy[v])) 54 { 55 cy[v]=u; cx[u]=v; 56 return 1; 57 } 58 } 59 } 60 return 0; 61 } 62 void maxmatch() 63 { 64 ans=0; 65 memset(cx,-1,sizeof(cx)); 66 memset(cy,-1,sizeof(cy)); 67 while(searchpath()) 68 { 69 memset(bmask,0,sizeof(bmask)); 70 for(int i=1;i<=nx;i++) 71 if(cx[i]==-1) ans+=findpath(i); 72 } 73 } 74 void init() 75 { 76 for(int i=0;i<=N;i++) bmap[i].clear(); 77 } 78 char s[605][605]; 79 int Map[605][605]; 80 int main() 81 { 82 //freopen("test.txt","r",stdin); 83 int cas,n,i,j,k=1,a,b,t=1; 84 char ch; 85 scanf("%d",&cas); 86 while(cas--) 87 { 88 scanf("%d",&n); 89 t=0; 90 for(i=1;i<=n;i++){ 91 getchar(); 92 for(j=1;j<=n;j++) 93 { 94 scanf("%c",&s[i][j]); 95 if(s[i][j]==‘#‘) Map[i][j]=++t; 96 } 97 } 98 init(); 99 for(i=1;i<=n;i++)100 {101 for(j=1;j<=n;j++)102 {103 if(s[i][j]==‘#‘&&((i+j)%2))104 {105 a=Map[i][j];106 if(i>1&&s[i-1][j]==‘#‘){107 b=Map[i-1][j];108 bmap[a].push_back(b);109 }110 if(i<n&&s[i+1][j]==‘#‘){111 b=Map[i+1][j];112 bmap[a].push_back(b);113 }114 if(j>1&&s[i][j-1]==‘#‘){115 b=Map[i][j-1];116 bmap[a].push_back(b);117 }118 if(j<n&&s[i][j+1]==‘#‘){119 b=Map[i][j+1];120 bmap[a].push_back(b);121 }122 }123 }124 }125 nx=t;126 maxmatch();127 printf("Case %d: %d\n",k++,ans);128 }129 return 0;130 }
4185 Oil Skimming 最大匹配 奇偶建图
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。