Uva11419 I AM SAM 我是山姆二分匹配

这是白书上给出的题目，我去做了下，题意跟poj3041很像，给一个矩阵，再给出障碍物，一个子弹可以清除一整行或者一整列的障碍物，问最少需要打几枪，同时把开枪的位置给输出来，

分析：求打几枪很简单，先做一下poj3041就知道了，最少打几枪反过来想其实就是问最多有几个点不在同一个行也不在同一列上，至于开枪的位置，可以开两个数组，这里是行与列进行匹配，所以行在左集合列右集合，各自开一个数组 marry[],marry[i]=x,择表示i与x进行匹配，求最大匹配数完成后，再从没有匹配的点开始拓展，因为求最少开几枪其实就是求最大匹配数，最大匹配数就是最多有几个点不在同一行也不在同一列，那么剩下的点就是没有匹配过，那就从他们开始拓展开来，第一次没有参与匹配的点在哪一行最多或者在哪一列最多那么肯定开枪位置就在这一行或者这一列，这里的左右集合表现的很明显，因为记录路径的缘故

#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
  
#define ll long long  
#define LL __int64  
#define eps 1e-8  
const ll INF=9999999999999;  
  
using namespace std;  
  
#define M 400000100  
  
#define inf 0xfffffff  
  
//vector > G;  
//typedef pair P;  
//vector> ::iterator iter;  
//  
//mapmp;  
//map::iterator p;  
  
vectorG[1212];  
  
char tempmp[1212];  
int mp[1212][1212];  
int lmarry[1212],rmarry[1212];  
bool visl[1212],visr[1212];  
  
int dis[2][4]={0,-1,0,1,1,0,-1,0};  
  
int n,m,k;  
  
void clear()  
{  
    memset(lmarry,-1,sizeof(lmarry));  
    memset(rmarry,-1,sizeof(rmarry));  
    memset(visl,false,sizeof(visl));  
    memset(visr,false,sizeof(visr));  
    memset(mp,0,sizeof(mp));  
    for(int i=0;i<1212;i++)  
        G[i].clear();  
}  
  
bool dfs(int x)  
{  
    visl[x]=true;  
    for(int i=0;i

Uva11419 I AM SAM 我是山姆 二分匹配