hdu 5093 二分匹配

hdu 5093 二分匹配

/*
題意：給你一些冰島。公共海域和浮冰，冰島可以隔開兩個公共海域，浮冰無影響
求選盡可能多的選一些公共海域點每行每列僅能選一個。
限制條件：冰山可以隔開這個限制條件。即*#*可以選兩個
預處理：
*****
**#*#
*****   可以按行轉化  

*****
**#oo
ooo*#
*****

按列轉化
***o**o
**ooooo
oooo*oo
**o**o*
因為每行每列頂多可以增加50
所以總共最多2500*2500的矩陣
然後直接二分匹配即可
*/
#include
#include
#define N  2800
int ma[N][N];
char s[60][60];
int ans[N][N];
int n,m,addx,addy;
void slovex() {//按行轉化
  int i,k;
  addx=0;
for(i=1;i<=n;i++) {
addx++;
 //printf("%d\n",addx);
 k=1;
while(1) {
    for(;s[i][k]!='#'&&k<=m;k++) {
      if(s[i][k]=='*')
       ans[addx][k]=1;
    }
    if(k==m)//最後一個也要算進去，剛開始這裡錯了一直沒看出來重要*****
        ans[addx][k]=2;
    if(k==m+1||k==m)
        break;
    ans[addx][k]=2;
    k++;
    addx++;
}
}
return ;
}
void slovey() {//在按行轉化的基礎上按列轉化
 int i,k;
 addy=0;
 for(i=1;i<=m;i++) {
    addy++;
    k=1;
 //   printf("%d\n",addy);
    while(1) {
        for(;ans[k][i]!=2&&k<=addx;k++) {
            if(ans[k][i]==1)
                ma[k][addy]=1;
        }
        if(k==addx+1||k==addx)
            break;
            k++;
        addy++;
    }
 }
 return;
}
int vis[N],link[N];
int findd(int u) {
int i;
for(i=1;i<=addy;i++)
if(ma[u][i]&&vis[i]==0) {
vis[i]=1;
if(link[i]==-1||findd(link[i])) {
link[i]=u;
return 1;
}
}
return 0;
}
int main() {
    int t,i,sum,j;
    scanf("%d",&t);
    while(t--) {
        scanf("%d%d",&n,&m);
        memset(ma,0,sizeof(ma));
        memset(ans,0,sizeof(ans));
        for(i=1;i<=n;i++)
            scanf("%s",s[i]+1);
        slovex();
       /*     for(i=1;i<=addx;i++) {
                for(j=1;j<=m;j++)
            printf("%d ",ans[i][j]);
            printf("\n");
        }*/
        slovey();
      /*   for(i=1;i<=addx;i++) {
                for(j=1;j<=addy;j++)
            printf("%d ",ma[i][j]);
            printf("\n");
        }*/
        memset(link,-1,sizeof(link));
        sum=0;
        for(i=1;i<=addx;i++) {//直接套模板二分匹配即可
            memset(vis,0,sizeof(vis));
            sum+=findd(i);
        }
    printf("%d\n",sum);
    }
return 0;}