首页 > 代码库 > HDU——2119 Matrix
HDU——2119 Matrix
题目大意：
给你一个矩阵（只包含0或1），每次你可以选择一行或一列，并删除这一行或这个列中的所有“1”。您的任务是给出删除矩阵中所有“1”的最小时间。
思路：
我们要将所有的1都删去，那样我们对于1的位置的行与列连边，再把这两个（列和边）看作是两个集合。求它的最大匹配数。
一个很简单的二分图的板子。。
代码：
#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>#include<algorithm>#define N 110using namespace std;bool vis[N];int n,m,ans,girl[N],map[N][N];int read(){ int x=0,f=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘) {if(ch==‘-‘) f=-1; ch=getchar();} while(ch<=‘9‘&&ch>=‘0‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}int find(int x){ for(int i=1;i<=m;i++) if(!vis[i]&&map[x][i]) { vis[i]=true; if(girl[i]==-1||find(girl[i]))//这个地方他不能是0，因为原来存的就是0与1 { girl[i]=x; return 1; } } return 0;}int main(){ while(1) { ans=0; memset(girl,-1,sizeof(girl)); memset(map,0,sizeof(map)); memset(map,0,sizeof(map)); n=read();if(!n) break; m=read(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) map[i][j]=read(); for(int i=1;i<=n;i++) { memset(vis,0,sizeof(vis)); if(find(i)) ans++; } printf("%d\n",ans); } return 0;}
HDU——2119 Matrix
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。