最小点覆盖集的裸题，只要“拆点建边”然后求出最大匹配，则：最小点覆盖集的大小 = 点数 - 最大匹配
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5 6 const int N = 121; 7 const int M = 5000; 8 bool visit[N]; 9 int mark[N]; 10 int head[N]; 11 int n, m, e; 12 13 void init() 14 { 15 e = 0; 16 memset( head, -1, sizeof(head) ); 17 } 18 19 struct Edge 20 { 21 int v, next; 22 } edge[M]; 23 24 void addEdge( int u, int v ) 25 { 26 edge[e].v = v; 27 edge[e].next = head[u]; 28 head[u] = e++; 29 } 30 31 int dfs( int u ) 32 { 33 for ( int i = head[u]; i != -1; i = edge[i].next ) 34 { 35 int v = edge[i].v; 36 if ( !visit[v] ) 37 { 38 visit[v] = 1; 39 if ( mark[v] == -1 || dfs(mark[v]) ) 40 { 41 mark[v] = u; 42 return 1; 43 } 44 } 45 } 46 return 0; 47 } 48 49 int solve() 50 { 51 int ans = n; 52 memset( mark, -1, sizeof(mark) ); 53 for ( int i = 1; i <= n; i++ ) 54 { 55 memset( visit, 0, sizeof(visit) ); 56 ans -= dfs(i); 57 } 58 return ans; 59 } 60 61 int main () 62 { 63 int t; 64 scanf("%d", &t); 65 while ( t-- ) 66 { 67 scanf("%d%d", &n, &m); 68 init(); 69 while ( m-- ) 70 { 71 int a, b; 72 scanf("%d%d", &a, &b); 73 addEdge( a, b ); 74 } 75 printf("%d ", solve()); 76 } 77 return 0; 78 }
hdu的数据也太弱了，一开始手误将dfs中的mark[v]写成了v居然都过了，后来交到poj死活过不去才发现是自己写错了，汗。