传送门
题目大意：有N个路口M条路。给出你每条路的起点和终点，让你求出最少要放几个士兵（每个士兵只能沿着一条路走且不能与其他士兵的路线有交集）才能走完整个图。
因为这是一道最小路径覆盖的裸题，所以我就写一下自己的理解。
做最小路径覆盖，首先要拆点，把每个点拆成两个，一个表示出，，一个表示进。然后进行最大匹配，因为二分图每一个顶点都只能有一条匹配边，所以保证了路径不交叉。
对于结论：最小路径覆盖数 = 顶点数 – 拆点后的最大匹配数。这是因为匹配中的一条路径上的两个点是拆点之后的两个点，相当于原图中的两个1/2点。所以总的顶点数 – 最大匹配数才等于最小路径覆盖数。
struct node{int v;node *next;}Edge[MAXM*2], *Adj[MAXN*2], *Mcnt = Edge;void Addedge(int u, int v){node *t = ++Mcnt;t->v = v;t->next = Adj[u];Adj[u] = t;}int n, m, c[MAXN *2], cnt;bool vis[MAXM];bool dfs(int u){vis[u] = 1;for(node *p = Adj[u]; p; p = p->next){if(vis[p->v]) continue;vis[p->v] = 1;if(!c[p->v] || dfs(c[p->v])){c[u] = p->v;c[p->v] = u;return 1;}}return 0;}int main(){int T;scanf(“%d”, &T);while(T –){Mcnt = Edge;memset(Adj, 0, sizeof Adj);int a, b;cnt = 0;scanf(“%d%d”, &n, &m);for(int i = 1; i <= m; i ++){scanf(“%d%d”, &a, &b);Addedge(a, b + n);}memset(c, 0, sizeof c);int ans = 0;for(int i = 1; i <= n; i ++)if(!c[i]){memset(vis, 0, sizeof vis);ans += dfs(i);}printf(“%d\n”, n – ans);}return 0;}
空虚无聊的时候就读书，但一定得有自己的生活目标和计划。
