hdu 1151 Air Raid（最小路径覆盖）

Air Raid

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1313????Accepted Submission(s): 831

#include <iostream>#include <stdio.h>#include <memory.h>#include <vector>using namespace std;const int N = 125;int pre[N];bool flag[N];vector<int> map[N];int n;int find(int cur){ int i, k; for(i = 0; i < map[cur].size(); i++) { k = map[cur][i]; if(!flag[k]) { flag[k] = true; if(pre[k] == -1 || find(pre[k])) { pre[k] = cur; return 1; } } } return 0;}int main(){ int i, t, s, e, num, sum; scanf("%d", &t); while(t--) { memset(pre, -1, sizeof(pre)); for(i = 1; i <= n; i++) map[i].clear(); scanf("%d", &n); scanf("%d", &num); for(i = 1; i <= num; i++) { scanf("%d %d", &s, &e); map[s].push_back(e); } sum = 0; for(i = 1; i <= n; i++) { memset(flag, false, sizeof(flag)); sum += find(i); } printf("%d\n", n - sum); } return 0;}?