转载

--hdu 1151 - > 双向路径搜索解决覆盖问题

伞兵可以降落到图上的任意一个点，用最少的伞兵在单向道路上走完所有的点

解决：对一个点双向dfs，目的在于找到任意一个其他伞兵未访问的非起点，只要找到这个点，则可以保证这条路径是最佳的；

因为路是单向的，所以从这个点出发后，就不会再次回到这个点（题目中保证没有环）。

#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int ms[125][125]; int vis[125]; int n,m; bool dfs(int u){     bool wala = false;     for(int i = 1;i<=n;i++){  if(vis[i] == 0 &&ms[u][i]){      vis[i] = 1;      dfs(i);      wala = true;      break;  }else if(ms[u][i] && dfs(i)){      wala = true;      break;  }     }     return wala; } bool re_dfs(int u){     bool wala = false;     for(int i = 1;i<=n;i++){  if(vis[i] == 0&&ms[i][u]){      vis[i] = 1;      re_dfs(i);      wala = true;      break;  }else if(ms[i][u] &&re_dfs(i)){      wala = true;      break;  }     }     return wala; } int main(){      int t ;      scanf("%d",&t);      while(t--){  int ans = 0;  memset(ms,0,sizeof(ms));  memset(vis,0,sizeof(vis));  scanf("%d%d",&n,&m);  int u,v;  for(int i = 0;i<m;i++){      scanf("%d%d",&u,&v);      ms[u][v] = 1;  }  for(int  i = 1;i <= n;i++){      if(!vis[i]){   vis[i] = 1;   dfs(i);   re_dfs(i);   ans ++;      }  }  printf("%d/n",ans);      } }