Matrix
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1376 Accepted Submission(s): 599
Problem Description
Give you a matrix(only contains 0 or 1),every time you can select a row or a column and delete all the '1' in this row or this column .
Your task is to give out the minimum times of deleting all the '1' in the matrix.
Input
There are several test cases.
The first line contains two integers n,m(1<=n,m<=100), n is the number of rows of the given matrix and m is the number of columns of the given matrix.
The next n lines describe the matrix:each line contains m integer, which may be either 『1』 or 『0』.
n=0 indicate the end of input.
Output
For each of the test cases, in the order given in the input, print one line containing the minimum times of deleting all the '1' in the matrix.
Sample Input
3 3 0 0 0 1 0 1 0 1 0 0
Sample Output
2這題大概意思就是給你一個n*m只由0和1組成的矩陣，你可以劃掉任意一行或者一列的數字1，問你把矩陣內的1全部劃掉最少需要幾步？這個題明顯的思路是：二分最大匹配，即用匈牙利演算法求最大匹配，怎樣匹配呢？就是把矩陣的行看做boy，把矩陣的列看做girl，如果矩陣中有數字1，表明這個行（boy）和這個列（girl）想在一起，所以轉化一下就是成了HDU上「過山車」這道題了AC代碼+解釋：#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<iomanip> #include<queue> #include<stack> #include<set> #include<cmath> #include<map> #include<algorithm> const int MAX=101; int Map[MAX][MAX]; int girl[MAX];//女生 int boy[MAX];//男生 int mark[MAX];//匹配好了就標記 int pipei[MAX];//誰跟誰匹配，例如pipei[1]=2表示男生1號匹配的是2號女生 int g;//表示女生的個數 int b;//表示男生個數 using namespace std; bool find(int x)//尋找男生 { int i; for(i=0;i<b;i++) { if(Map[boy[i]][x]==1&&!mark[boy[i]]) { mark[boy[i]]=1; if(pipei[boy[i]]==-1||find(pipei[boy[i]]))//如果該男生沒有被匹配或者已經匹配了但是跟這個男生匹配的女生還有別的男生可以匹配那麼就把這個男生讓出來 { pipei[boy[i]]=x;//匹配 return true; } } } return false; } int main() { int n,m,sum,i,j; while(cin>>n,n) { cin>>m; memset(Map,0,sizeof(Map));//初始化 memset(pipei,-1,sizeof(pipei));//同上 map<int,int>B;//這裡開map容器是記錄所有男生以免重複記錄 map<int,int>G;//同上 g=0; b=0; for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { cin>>Map[i][j]; if(Map[i][j]==1) { if(B[i]==0)//如果這個男生沒有被記錄 { B[i]++;//就加進來並且標記已加入 boy[b++]=i; } if(G[j]==0)//同上 { G[j]++; girl[g++]=j; } } } } sum=0; for(i=0;i<g;i++)//女生開始匹配男生 { memset(mark,0,sizeof(mark)); if(find(girl[i]))//如果可以匹配就+1 sum+=1; } cout<<sum<<endl; } return 0; }