1、最小顶点覆盖 = 最大匹配数
最小顶点覆盖：实质是个点集，点集里面的点能覆盖所有的边，最小点覆盖就是满足这个要求的点集中点数最小的那个
2、最大独立集 = 顶点个数V - 最大匹配数
最大独立集：实质是个点集，点集里面的点互相之间不连着，最大独立集就是满足这个要求的点集中点数最多的那个
3、最小边覆盖 = 顶点个数V - 最大匹配数
最小边覆盖：实质是个边集，这个集合里的边能覆盖所有的点，最小边覆盖是满足这个要求的所有边集中边数最少的一个
这里顶点数等于总的顶点数
HDU 1150 （最小顶点覆盖） #include <iostream> #include <stdio.h> #include <algorithm> #include <string.h> using namespace std; int Map[105][105]; int match[105]; ///匹配 int vis[105]; ///访问 int n,m; int Find(int x){ for(int i=1; i<=m; i++) if(vis[i] == 0 && Map[x][i]){ vis[i] = 1; if(match[i] == -1 || Find(match[i])){ match[i] = x; return 1; } } return 0; } int main() { int k; while(1){ scanf("%d", &n); if(!n) break; scanf("%d%d", &m, &k); memset(Map, 0, sizeof Map); memset(match, -1, sizeof match); for(int i=0; i<k; i++){ int a,b,c; scanf("%d%d%d", &a, &b, &c); Map[b][c] = 1; } int ans = 0; for(int i=1; i<=n; i++){ memset(vis, 0, sizeof vis); if(Find(i)) ans++; } printf("%d\n", ans); } return 0; }
