poj2226 Muddy Fields 填充棒子（二分匹配）

参考博客：https://blog.csdn.net/liujc_/article/details/51287019

参考博客：https://blog.csdn.net/acdreamers/article/details/8621130

题目来源：http://poj.org/problem?id=2226

题意：

给你一个地图，用宽为一长随意的棒子横或竖地填满所有的  “*”   且不能填”.“

求最少的棒子数

题解：

每个* 都有一个需求，即有横的或竖的棒子经过它，对于每个点，建立一条边和两个二分图的点。求最小顶点覆盖==最大匹配

#include<iostream>

#include<cstdio>

#include<vector>

using namespace std;

char ma[55][55];

int match[55*55];

int n,m;

bool used[55*55];

vector<int>g[55*55];

bool dfs(int x)

{

	 if(used[x])return 0;

	 used[x]=1;

     for(int i=0;i<g[x].size();i++)

	 {

			int V=g[x][i];

			if(match[V]==0||dfs(match[V]))

			{

				match[V]=x;

				return 1;

			}

	 }

	 return 0;

}

int guar()

{

    int res=0;

	for(int i=1;i<=n*m;i++)

	{

        for(int j=1;j<=n*m;j++)used[j]=0;

		if(dfs(i))res++;

	}

	return res;

}

int main()

{

	while(cin>>n>>m)

	{

        for(int i=0;i<55*55;i++)

		{

			g[i].clear();

			match[i]=0;

		}

       // cout<<n<<" "<<m<<endl;

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

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

				cin>>ma[i][j];

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

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

	    {

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

				{

					int y=i,x=j;

					while(x>1&&ma[i][x-1]=='*')x--;

					while(y>1&&ma[y-1][j]=='*')y--;

                    g[(i-1)*m+x].push_back((y-1)*m+j);

				}

	    }

		cout<<guar()<<endl;

	}

}