HDU2119 Matrix 很经典的做法 二分匹配最大匹配数

这道题目跟poj3041一模一样，没有任何区别， 因为一次可以消除某一整行 或者 某一整列的1，所以题目可以反过来想，最多有多少个 1 既不在同一行也不在同一列，这样就可以进行行列匹配，求最大匹配数即最多有多少个 1 既不在同一行也不在同一列， 做出后记得关注一下poj2226，那道题目可以转化为本道题目，那个方法很经典，同时也让我认识到了最小路径覆盖 的正确使用，印象很是深刻

#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];int mp[1212][1212];int marry[1212];bool vis[1212];int vmax,vmin,l,r,mid;int dis[2][4]={0,-1,0,1,1,0,-1,0};int n,m,k;void clear(){memset(marry,-1,sizeof(marry));memset(vis,false,sizeof(vis));memset(mp,0,sizeof(mp));for(int i=0;i<1212;i++)G[i].clear();}bool dfs(int x){for(int i=0;i<m;i++){if(mp[x][i] && !vis[i]){vis[i]=true;if(marry[i]==-1 || dfs(marry[i])){marry[i]=x;return 1;}}}return 0;}int main(void){while(scanf("%d",&n),n){clear();scanf("%d",&m);for(int i=0;i<n;i++)for(int j=0;j<m;j++)cin>>mp[i][j]; int ans=0;for(int i=0;i<n;i++)//直接进行行列匹配{memset(vis,false,sizeof(vis));if(dfs(i))ans++;}cout<<ans<<endl;}}