Battle ships HDU - 5093二分匹配

Battle shipsHDU - 5093

　　题目大意：n*m的地图，*代表海洋，#代表冰山，o代表浮冰，海洋上可以放置船舰，但是每一行每一列只能有一个船舰（类似象棋的車）,除非同行或者同列的船舰中间有冰山挡着，问最多能放多少个船舰？

　　之前做过一个放置炮的，那时数据小直接暴力加搜索就A了，然而这题暴力搜索的话，直接了当的TLE，没办法只好去学新东西了。二分图这个概念只有在之前的题目中做过匈牙利的板子题，可是具体概念和思路并不了解，这题也正好提醒了我去深入了解。但最近需要做的事情较大，一直想整理的一些算法和模板总结也暂时拖一拖。

　　回到这题，为什么可以用二分匹配做呢，首先如果没有障碍全是海的话，那就刚好是每一行每一列只能放一个，那我们分配的时候就是给每一行分配一列，这样一行一列刚好对应了放置的位置，而这个给每一行分配一列的过程刚好也可以用二分匹配实现。那么多了障碍之后，该如何处理呢，其实也就是一行分成多行，我们把相同行的统一编号化成一块区域，举个例子，比如2*6的地图

　　******

　　之前每个点对行编号就是

　　111111

　　而多了障碍之后

　　***#**

　　**#***

　　这时的编号就是

　　111022

　　330444

　　列的处理也是类似，列的编号就是

　　123056

　　120456

　　有了编号之后，我们就可以根据共同点连边，像行编号为1的点和列编号为1,2,3的点有公共点，那么它们可以连边。上图每个行块可以连的列块就是

　　1:1 2 3

　　2:5,6

　　3:1,2

　　4:4,5,6

　　这时我们就是尽可能多的给每一个行快分配一个列块，这样就可以得到最多的点，也就是最多能放置的数目。

 #include<cstdio>

 #include<cstring>

 #include<vector>

 using namespace std;

 char s[][];

 int x,y,xid[][],yid[][],cj[],vis[];

 vector<int> vv[];

 bool match(int u)

 {

     for(int i=;i<vv[u].size();i++)

     {

         int v=vv[u][i];

         if(!vis[v])//这个列还没遍历过

         {

             vis[v]=;

             if(!cj[v]||match(cj[v]))//这个列块还没分配给某个行块

             {//或者它分配给的行块可以匹配其他列块

                 cj[v]=u;

                 return ;

             }

         }

     }

     return ;

 }

 int main()

 {

     int t,n,m;

     scanf("%d",&t);

     while(t--)

     {

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

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

             scanf("%s",s[i]);

         memset(xid,,sizeof(xid));

         memset(yid,,sizeof(yid));

         x=,y=;

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

         {

             int j=,is=;

             while(j<m)

             {

                 if(s[i][j]=='#')

                     is=;

                 while(j<m&&s[i][j]=='#')

                     j++;

                 if(s[i][j]=='*')

                 {

                     if(!is)

                         x++;

                     is=;

                     xid[i][j]=x;

                 }

                 j++;

             }

         }//给每个行块编号

         for(int i=;i<m;i++)

         {

             int j=,is=;

             while(j<n)

             {

                 if(s[j][i]=='#')

                     is=;

                 while(i<n&&s[j][i]=='#')

                     j++;

                 if(s[j][i]=='*')

                 {

                     if(!is)

                         y++;

                     is=;

                     yid[j][i]=y;

                 }

                 j++;

             }

         }//给每个列块编号

         for(int i=;i<=x;i++)

             vv[i].clear();

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

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

                 if(s[i][j]=='*')//二分图加边

                     vv[xid[i][j]].push_back(yid[i][j]);

         int ans=;

         memset(cj,,sizeof(cj));

         for(int i=;i<=x;i++)//匈牙利算法模板

         {

             memset(vis,,sizeof(vis));

             ans+=match(i);

         }

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

     }

     return ;

 }

门泊东吴万里船

　　感觉二分匹配难在怎么想到这个建边

巴特西

Battle ships HDU - 5093二分匹配

Battle shipsHDU - 5093

最新文章

热门文章