成都网站建设 工资/自媒体培训

传送门

题目大意：有N个路口M条路。给出你每条路的起点和终点，让你求出最少要放几个士兵（每个士兵只能沿着一条路走且不能与其他士兵的路线有交集）才能走完整个图。

因为这是一道最小路径覆盖的裸题，所以我就写一下自己的理解。

做最小路径覆盖，首先要拆点，把每个点拆成两个，一个表示出，一个表示进。然后进行最大匹配，因为二分图每一个顶点都只能有一条匹配边，所以保证了路径不交叉。

对于结论：最小路径覆盖数 = 顶点数 - 拆点后的最大匹配数。这是因为匹配中的一条路径上的两个点是拆点之后的两个点，相当于原图中的两个1/2点。所以总的顶点数 - 最大匹配数才等于最小路径覆盖数。

---

#include<cstdio>
#include<cstring>
#define MAXN 150
#define MAXM 30000
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;
}