題目鏈接：http://poj.org/problem?id=2226
最小函數依賴集和正則覆蓋？ 這題是POJ 3041的升級版本，很有意思，要求木板不能蓋在草地上。那么這里我們可以把每行一連續‘*’的看做行，把每列連續的‘*’看做列，那么在建模就是POJ 3041的原題了。
看一個例子：
poj2352、 3 3 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?X集合 ? ? ? Y集合
.*. ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 010 ? ? ? ? ?020
*** ? ? ?———> ? ? ? ? ? ? 222? ? ? ? ? 123
.*. ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 033 ? ? ? ? ?020
那么再根據X，Y集合連邊即可。
要覆蓋圖中所有的點，即二分圖中的邊，那么就是最小點集覆蓋了。
1 //STATUS:G++_AC_16MS_1760KB 2 #include<stdio.h> 3 #include<stdlib.h> 4 #include<string.h> 5 #include<math.h> 6 #include<iostream> 7 #include<string> 8 #include<algorithm> 9 #include<vector> 10 #include<queue> 11 #include<stack> 12 using namespace std; 13 #define LL long long 14 #define Max(a,b) ((a)>(b)?(a):(b)) 15 #define Min(a,b) ((a)<(b)?(a):(b)) 16 #define mem(a,b) memset(a,b,sizeof(a)) 17 #define lson l,mid,rt<<1 18 #define rson mid+1,r,rt<<1|1 19 const int MAX=60,INF=200000000; 20 21 char map[MAX][MAX]; 22 int g[510][510],vis[510],y[510],grax[MAX][MAX],gray[MAX][MAX]; 23 int n,m,cou; 24 25 void getg() 26 { 27 mem(grax,0); 28 mem(gray,0); 29 int i,j,k; 30 for(k=i=0;i<n;i++){ 31 for(j=0;j<m;j++){ 32 if(map[i][j]=='*'){ 33 k++; 34 for(;map[i][j]=='*';j++) 35 grax[i][j]=k; 36 } 37 } 38 } 39 cou=Max(cou,k); 40 for(k=j=0;j<m;j++){ 41 for(i=0;i<n;i++){ 42 if(map[i][j]=='*'){ 43 k++; 44 for(;map[i][j]=='*';i++) 45 gray[i][j]=k; 46 } 47 } 48 } 49 cou=Max(cou,k); 50 for(i=0;i<n;i++){ 51 for(j=0;j<m;j++){ 52 if(grax[i][j] && gray[i][j]) 53 g[grax[i][j]][gray[i][j]]=1; 54 } 55 } 56 } 57 58 int dfs(int u) 59 { 60 int v; 61 for(v=1;v<=cou;v++){ 62 if(g[u][v] && !vis[v]){ 63 vis[v]=1; 64 if(!y[v] || dfs(y[v])){ 65 y[v]=u; 66 return 1; 67 } 68 } 69 } 70 return 0; 71 } 72 73 int main() 74 { 75 // freopen("in.txt","r",stdin); 76 int i,j,ans; 77 while(~scanf("%d%d",&n,&m)) 78 { 79 ans=cou=0; 80 mem(y,0); 81 mem(g,0); 82 for(i=0;i<n;i++){ 83 scanf("%s",map[i]); 84 } 85 86 getg(); 87 for(i=1;i<=cou;i++){ 88 mem(vis,0); 89 if(dfs(i))ans++; 90 } 91 92 printf("%d\n",ans); 93 } 94 }
?
