题目大意：
有n个城市，m条道路，城市的道路是单向。
现在我们的伞兵要降落在城市里，然后我门的伞兵要搜索所有道路。问我们最少占领多少个城市就可以搜索所有的道路了。
我们可以沿着道路向前走到达另一个城市。
题目分析：
这道题目其实就是求最小路径覆盖
最小路径覆盖问题：用尽量少的不相交简单路径覆盖有向无环图的所有顶点。
将每个顶点分为两个，分别在X集合和Y集合中，如果存在有向边(a,b)，对应在二分图中有（Xa,Yb）
最小路径数=节点数-最大匹配
简单解释：
原图的路径覆盖和新图的匹配间有对应关系：
每条覆盖边都是匹配中的一条边，且只有路径的最后一个点
路径要求不能相交，恰好对应于匹配中两匹配边不能有公共端点。
于是求最大匹配后，不能被匹配上的点，即是路径的最后一个点。有多少个不能被匹配的点，就有多少条路径存在。
路径数=原点数－匹配边数。因此我们使匹配边数最大，即是使路径数最小。
#include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> #include<vector> #include<queue> #include<cmath> using namespace std; #define INF 0x3fffffff #define maxn 1705 int n, P[maxn], Head[maxn], m, k; bool vis[maxn]; struct EdgeNode { int e, next; }edge[maxn*5]; void AddEdge(int s, int e) { edge[k].next = Head[s]; edge[k].e = e; Head[s] = k ++; } void DFS2(int u) { } bool Find(int u) { for(int i=Head[u]; i!=-1; i=edge[i].next) { int v = edge[i].e; if(!vis[v] ) { vis[v] = true; if(P[v] == -1 || Find(P[v]) ) { P[v] = u; return true; } } } return false; } int solve() { int ans = 0; memset(P, -1, sizeof(P)); for(int i=1; i<=n; i++) { memset(vis, false, sizeof(vis)); if( Find(i) ) ans ++; } return n - ans; } int main() { int T; scanf("%d", &T); while(T--) { scanf("%d %d",&n, &m); int a, b; k = 0; memset(Head, -1, sizeof(Head)); for(int i=0; i<m; i++) { scanf("%d %d",&a, &b); AddEdge(a, b); } printf("%d ", solve() ); } return 0; }