Uva11419 I AM SAM 我是山姆 二分匹配
这是白书上给出的题目，我去做了下，题意跟poj3041很像，给一个矩阵，再给出障碍物，一个子弹可以清除一整行或者一整列的障碍物，问最少 需要打几枪，同时把开枪的位置给输出来，
分析：求打几枪 很简单，先做一下poj3041就知道了， 最少打几枪 反过来想 其实就是问 最多有几个点 不在同一个行也不在同一列上，至于开枪的位置，可以开两个数组，这里是行与列进行匹配，所以 行 在左集合 列右集合，各自开一个数组 marry[],marry[i]=x,择表示i与x进行匹配，求最大匹配数完成后，再从没有匹配的点开始拓展，因为求最少开几枪其实就是求最大匹配数，最大匹配数就是最多有几个点不在同一行也不在同一列，那么剩下的点就是没有匹配过，那就从他们开始拓展开来，第一次没有参与匹配的点 在哪一行最多 或者在哪一列最多 那么肯定开枪位置就在这一行 或者这一列，这里的左右集合表现的很明显，因为记录 路径的缘故
#include<iostream>#include<cstdio>#include<list>#include<algorithm>#include<cstring>#include<string>#include<queue>#include<stack>#include<map>#include<vector>#include<cmath>#include<memory.h>#include<set>#define ll long long#define LL __int64#define eps 1e-8const ll INF=9999999999999;using namespace std;#define M 400000100#define inf 0xfffffff//vector<pair<int,int> > G;//typedef pair<int,int> P;//vector<pair<int,int>> ::iterator iter;////map<ll,int>mp;//map<ll,int>::iterator p;vector<int>G[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<G[x].size();i++){int v=G[x][i];if(!visr[v]){visr[v]=true;if(lmarry[v]==-1 || dfs(lmarry[v])){lmarry[v]=x;rmarry[x]=v;return 1;}}}return 0;}int main(void){while(scanf("%d %d %d",&n,&m,&k),n+m+k){clear();int u,v;for(int i=0;i<k;i++){scanf("%d %d",&u,&v);G[u].push_back(v);//用邻接表比较快，邻接表记录也比较方便}int ans=0;for(int i=1;i<=n;i++)//跟poj3041一模一样的 反过来想其实就是求最多有几个点不在同一行也不在同一列上{memset(visr,false,sizeof(visr));if(dfs(i))ans++;}printf("%d",ans);memset(visl,false,sizeof(visl));memset(visr,false,sizeof(visr));for(int i=1;i<=n;i++)if(rmarry[i]==-1)//从没有匹配过的点开始拓展，再次匹配dfs(i);for(int i=1;i<=n;i++)//没有被匹配过的行，也就是左集合中的点输出if(!visl[i])printf(" r%d",i);for(int i=1;i<=m;i++)//被匹配上的列，也就是右集合中的点if(visr[i])printf(" c%d",i);printf("\n");}}