HDU1151 Air Raid

题目链接：https://vjudge.net/problem/HDU-1151

题目大意：

　　这个问题本质上就是有向图的最小不相交路径覆盖问题，在此推荐一篇博客。

知识点：　　最小路径覆盖

解题思路：

　　 $V_{x}$

AC代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 
 5 using namespace std;
 6 const int maxn=200;
 7 bool to[maxn][maxn], used[maxn];
 8 int go[maxn];
 9 
10 bool finds(int x,int n){
11     for(int j=1;j<=n;j++){
12         if(to[x][j]&&!used[j]){
13             used[j]=true;
14             if(go[j]==0||finds(go[j],n)){
15                 go[j]=x;
16                 return true;
17             }
18         }
19     }
20     return false;
21 }
22 int main()
23 {
24     int u,v;
25     int T,n,m;
26     scanf("%d",&T);
27     while(T--){
28         memset(go,0,sizeof(go));
29         memset(to,false,sizeof(to));
30         scanf("%d%d",&n,&m);
31         while(m--){
32             scanf("%d%d",&u,&v);
33             to[u][v]=true;
34         }
35         int all=0;
36         for(int i=1;i<=n;i++){
37             memset(used,false,sizeof(used));
38             if(finds(i,n))    all++;
39         }
40         printf("%d
",n-all);
41     }
42     return 0;
43 }

“这些年我一直提醒自己一件事情，千万不要自己感动自己。大部分人看似的努力，不过是愚蠢导致的。什么熬夜看书到天亮，连续几天只睡几小时，多久没放假了，如果这些东西也值得夸耀，那么富士康流水线上任何一个人都比你努力多了。人难免天生有自怜的情绪，唯有时刻保持清醒，才能看清真正的价值在哪里。”