HDU 2119 最小点覆盖问题
//HDU 2119//题意概述：给出一个N*M的01矩阵，每一次可以删除一行或者一列里面的所有1，问最少要删除几次才能让矩阵全为零//一开始没往二分图的方向思考。。。看见数据小暴力了一下TLE。。。//其实是二分图的最小点覆盖问题，行作为二分图的一部分，列作为二分图的另一部分。#include<iostream>#include<vector>using namespace std;const int MAXN = 100 + 10;bool used[MAXN];int link[MAXN];int n;vector<int> Map[MAXN];//匈牙利bool FindPath(int u){int size = Map[u].size();for(int i = 0; i<size; i++){int v = Map[u][i];if(!used[v]){used[v] = true;if(link[v]==-1 || FindPath(link[v])){link[v] = u; return true;}}}return false;}int solve(){int count = 0;for(int i = 0; i<n; i++){memset(used, 0, sizeof(used));if(FindPath(i))count++;}return count;}int main(){int m;int temp;while(scanf("%d", &n) != EOF, n){scanf("%d", &m);for (int j = 0; j<n; j++)Map[j].clear();for (int i = 0; i<n; i++){for (int j = 0; j<m; j++){cin>>temp;if (temp)Map[i].push_back(j);}}memset(link, -1, sizeof(link));cout<<solve()<<endl;}return 0;}