巢穴

about:blank

P3020

2分图
构图
两个集合是一样的,都是所有的*号
如果某两个*之间挨着,就连线
求最大匹配
可以轻易得出这个最大匹配把每个*都求了2遍
因此除以2,再加上未匹配的*,得解..
难点就是构图..
事实上匹配,网络流等的难点也就是构图

#include <iostream>
//#include <fstream>
using namespace std;
//ifstream fin("t3020.in");
struct node
{
 
int x,y;
}
;
const int MAXN=401;
node edge[MAXN];
bool connect[MAXN][MAXN];
bool hash[MAXN];
int v[MAXN];
int n;
int h,w;
int len;

bool find(int x)
{
     
for (int i=1;i<=len;i++)
     
{
         
if (!connect[x][i]) continue;
         
if (!hash[i])
         
{
          hash[i]
=true;
          
if (v[i]==0||find(v[i]))
          
{
           v[i]
=x;
           
return true;
          }

         }

     }

     
return false;
}

int main()
{
    cin
>>n;
    
while(n--)
    
{
     cin
>>h>>w;
     len
=0;
     
for (int i=1;i<=h;i++)
      
for (int j=1;j<=w;j++)
      
{
       
char ch;
       cin
>>ch;
       
if ('*'==ch)
       
{
        len
++;
        edge[len].x
=i;
        edge[len].y
=j;
       }

      }

     
     
//init
     memset(connect,0,sizeof(connect));
     
for (int i=1;i<=len;i++)
      
for (int j=1;j<=len;j++)
      
{
       
if (i==j) continue;
       
if (1==abs(edge[i].x-edge[j].x)+abs(edge[i].y-edge[j].y))
          connect[i][j]
=true;
      }

     
     
//
     memset(v,0,sizeof(v));
     
int answer=0,ans=0;
     
for (int i=1;i<=len;i++)
     
{
      memset(hash,
0,sizeof(hash));
      
if (find(i)) answer++;
      
else
       ans
++;
     }

     cout
<<answer/2+ans<<endl;
    
// system("pause");
    }

    
return 0;
}


 

posted on 2009-10-08 11:58 Vincent 阅读(99) 评论(0)  编辑 收藏 引用 所属分类: 数据结构与算法


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理