hdu 5093 Battle ships 匈牙利 很巧妙的建图思路

//这题逼我把匈牙利学了 之前一直很勤快敲网络流 而且不以为耻反以为荣

解：首先按行扫描编号，如果在同一块中（即可以相互攻击），那么将其标为相同的数组，对列也做同样的操作。

然后扫描整张图，如果行编号为a的块与列编号为b的块有公共点，那么将二部图中A集合中a点与B集合中b点相连。最后求出来最大二分匹配数就是答案。

（为什么这样做）首先很明显的，二部图中每一条边就对应原图中的一个点，因此，匹配数=边数=最多可放置的战舰数，另外二分图每个点只能匹配一次，对应到原题中就是每一块只能放置一个战舰.

 #include<cstdio>

 #include<iostream>

 #include<cmath>

 #include<algorithm>

 #include<cstring>

 #include<cstdlib>

 #include<queue>

 #include<vector>

 #include<map>

 #include<stack>

 #include<string>

 using namespace std;

 const int INF=;

 int T;

 int n,m,num_a,num_b;

 char c[][];

 int a[][];

 int b[][];

 bool adj[];

 int link[];

 int f[][];

 bool used[];

 bool work(int x){

     for (int i=;i<=num_b;i++){

             if (f[x][i] && !adj[i]){

                     adj[i]=;

                     if (!used[i] || work(link[i])){

                             link[i]=x;

                             used[i]=;

                             return true;

                     }

             }

     }

     return false;

 }

 int main(){

     scanf("%d",&T);

     for (int cas=;cas<=T;cas++){

             scanf("%d%d",&n,&m);

             for (int i=;i<n;i++) scanf("%s",c[i]);

             memset(a,,sizeof(a));

             memset(b,,sizeof(b));

             int t=;

             bool flag=;

             for (int i=;i<n;i++){

                     if (flag){

                             t++;

                             flag=false;

                     }

                     for (int j=;j<m;j++){

                             if (c[i][j]=='*') {

                                     a[i][j]=t;

                                     flag=true;

                             }

                             if (flag && c[i][j]=='#'){

                                     flag=false;

                                     t++;

                             }

                     }

             }

             if (flag) t++;

             num_a=t-;

             t=;

             flag=;

             for (int j=;j<m;j++){

                     if (flag){

                             t++;

                             flag=false;

                     }

                     for (int i=;i<n;i++){

                             if (c[i][j]=='*') {

                                     b[i][j]=t;

                                     flag=true;

                             }

                             if (flag && c[i][j]=='#'){

                                     flag=false;

                                     t++;

                             }

                     }

             }

             if (flag) t++;

             num_b=t-;

             memset(used,,sizeof(used));

             memset(f,,sizeof(f));

             memset(link,,sizeof(link));

             for (int i=;i<n;i++){

                     for (int j=;j<m;j++){

                             if (a[i][j]!= && b[i][j]!=){

                                     f[a[i][j]][b[i][j]]=;

                             }

                     }

             }

             int ans=;

             for (int i=;i<=num_a;i++){

                     memset(adj,,sizeof(adj));

                     if (work(i)) ans++;

             }

             printf("%d\n",ans);

     }

     return ;

 }

 /*

 2

 4 4

 *ooo

 o###

 **#*

 ooo*

 4 4

 #***

 *#**

 **#*

 ooo#

 */