POJ 3020 Antenna Placement(二分图匈牙利算法)

题目网址: http://poj.org/problem?id=3020

题意：

用椭圆形去覆盖给出所有环（即图上的小圆点），有两种类型的椭圆形，左右朝向和上下朝向的，一个椭圆形最多可以覆盖相邻的两个小圆点。

思路：

将每个小圆点看作是一个顶点，因为一个椭圆只能覆盖两个小圆点，我们就可以把这个图看成一个二分图。将相邻的两个点，一个看作是X集合内顶点，另一个看成是Y集合内顶点。但要注意的是一个顶点可能不止和一个顶点想连（如上图情况），所以我们要把上述情况看作是一个无向图，而不是有向图。因为是无向图，所以最大匹配数要除以二。

这样我们就把问题转换成求最小边覆盖：即用最小的边将所有顶点覆盖。该值会等于顶点数-最大匹配数。至于求二分图的最大匹配数，直接用匈牙利算法即可。

代码：

 #include <cstdio>

 #include <cstring>

 #include <vector>

 using namespace std;

 int match[];

 struct node{

     int x,y;

 }dir[]={{,},{-,},{,},{,-}};

 vector<node>v;

 int n,m,cnt;

 char matrix[][];

 int mp[][];

 int book[];

 int e[][];

 void deal(){

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

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

             if(matrix[x][y]!='*')   continue;

             int i=mp[x][y];

             for (int d=,xx,yy; d<; d++) {

                 xx=x+dir[d].x;

                 yy=y+dir[d].y;

                 if(xx< || x>=n || yy< || yy>=m || matrix[xx][yy]!='*')    continue;

                 int j=mp[xx][yy];

                 e[i][j]=;

             }

         }

     }

 }

 int dfs(int u){

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

         if(!book[i] && e[u][i]){

             book[i]=;

             if(match[i]== || dfs(match[i])){

                 match[i]=u;

                 return ;

             }

         }

     }

     return ;

 }

 int main(){

     int t;

     scanf("%d",&t);

     while (t--) {

         int sum=;

         cnt=;

         v.clear();

         memset(match, , sizeof(match));

         memset(mp, , sizeof(mp));

         memset(e, , sizeof(e));

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

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

             gets(matrix[i]);

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

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

                     mp[i][j]=++cnt;

                 }

             }

         }

         deal();

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

             memset(book, , sizeof(book));

             if(dfs(i))  sum++;

         }

         printf("%d\n",cnt-sum/);

     }

     return ;

 }

巴特西

POJ 3020 Antenna Placement(二分图匈牙利算法)

最新文章

热门文章

巴特西

POJ 3020 Antenna Placement(二分图 匈牙利算法)

最新文章

热门文章

POJ 3020 Antenna Placement(二分图匈牙利算法)