用匈牙利就行，比較赤裸。

/** hdu2119/win.cpp* Created on: 2012-8-13* Author : ben*/ #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> using namespace std;const int MAXN = 210; int N, M, mymatch[MAXN]; bool visited[MAXN], mymap[MAXN][MAXN];bool buildgraph() {int t;scanf("%d", &N);if(N == 0) {return false;}scanf("%d", &M);memset(mymap, false, sizeof(mymap));for(int i = 0; i < N; i++) {for(int j = 0; j < M; j++) {scanf("%d", &t);if(t == 1) {mymap[i][j] = true;}}}return true; } bool dfs(int k) {int t;for (int i = 0; i < M; i++) {if (mymap[k][i] && !visited[i]) {visited[i] = true; t = mymatch[i]; mymatch[i] = k;if (t == -1 || dfs(t)) {return true;}mymatch[i] = t;}}return false; } int hungary () {memset(mymatch, -1, sizeof(mymatch));int ans = 0;for (int i = 0; i < N; i++) {memset(visited, false, sizeof(visited));if (dfs(i)) {ans++;}}return ans; }int main() { #ifndef ONLINE_JUDGEfreopen("data.in", "r", stdin); #endifwhile(buildgraph()) {printf("%d\n", hungary());}return 0; }

轉載于:https://www.cnblogs.com/moonbay/archive/2012/08/14/2638714.html

總結

以上是生活随笔為你收集整理的hdu 2119最小点集覆盖的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。