题目

题目

参考资料

小蓝本（算法进阶）

做法

前置芝士：有向无环图的最小路径点覆盖。

我们证明有向无环图的可重复点集的最小路径点覆盖的个数就是答案。

设路径集合为$path$，而藏身点集合为$hide$，$G^{\prime }$为$G$传递闭包后的图，$fa[x]$为$x$路径上往上一条边的点（而$x^{\prime }$是指往上不知多少边的点），$son[x]$类似，不过是往下一条边的。

首先，对于每一条最小路径，最多只能有一个藏身点，所以$|hide|\le |path|$，那么我们只要能够构造出一种$|hide|=|path|$的方案即可。

我们先求出$path$的具体方案，折在$x\in G^{\prime }$在拆点二分图$G_2^{\prime }$中对应左部点$x$和右部点$x^{\prime }$。

1. 依次考虑每一个非匹配点$x_0$。
2. 从$x_0$出发，不断访问$x_0,match[x_0^{\prime }],match[match[x_0^{\prime }{]}^{\prime }]...$，知道到达一个左部点$y_0$，满足它对应的右部点$y_0^{\prime }$是非匹配点。
3. 在$G^{\prime }$中，节点$x_0,y_0$以及刚才经过的点构成一条路径，$y_0$是起点，$x_0$是终点。

上面给出的所有路径就是覆盖$G^{\prime }$中所有点的一个方案，且路径互不相交。（所以终点也不相同）

现在给出$path$的每条路径上选出一个藏身点的方法：

1. 选出$path$中每条路径的终点$x_0$，构成集合$E$。
2. 求出从$E$中节点出发，走一条边，到达的节点结合$next(E)$。
3. 根据传递闭包的性质,$G$中任意两个藏身点没有路径相连，等价于$G^{\prime }$中任意两个藏身点都没有边相连，因此，若$E\cap next(E)=Ø$，则$hide=E$即为所求。
4. 否则，考虑$E\cap next(E)$中每个节点$e$，沿着 $e$所在的路径往上走，直到一个节点$e^{\prime }\notin next(E)$。从$E$中删掉$e$，加入$e^{\prime }$。
5. 对于修改后的集合$E$，重复执行步骤$34$，直至$3$中的条件满足。

那么现在需要证明第$4$步中，一定能找到合法的点$e^{\prime }$。

证明几个定理：

1. $E\cap next(E)$中两个点$x,y$，先跳$x$，删除$x$并加入$x^{\prime }$，一定有$y\in E^{\prime }\cap next(E^{\prime })$，不难证明$x$能到达$y$，$x^{\prime }$也能到达$y$，所以跳点的先后顺序并不会影响其中一个点少跳。
2. 对于$E\cap next(E)$中两个点$x,y$，如果$x$先跳会跳到$x^{\prime }$，$y$先跳会跳到$y^{\prime }$，而$y$在$x$跳完之后跳会跳到$y^{\prime \prime }$，这样说明$x$跳完后会导致$y$的多跳，但是因为如果$y$先跳，$x$后跳，这样因为$x^{\prime }$能指向$y^{\prime \prime }$也能指向$y^{\prime }$，所以$y$还是会跳到$y^{\prime \prime }$，所以跳的最终结果并不会变，只会改变跳的步骤次数（简单来说就是因为每个点不会少跳，所以最终都会跳，所以影响只分先后，不分是否）。
3. 上面两点说明这样构造的最终方案是唯一的，且跳的步骤先后没有影响，所以可以构造出一种跳点顺序$T$和影响方案（$x$能影响$y$当且仅当因为$x$能到达$y$，导致了$y$往上跳，定义为$x>>y$，但是不代表$x$能到达$y$就一定是$x>>y$，即最多一个点能影响$y$，同时不难看出如果$x>>y$必然存在$x->y$），不存在$t_i>>t_j(i>j)$。

好，那么对于一个点$e$，所在路劲$pe$，如果$e$跳到了起点都不符合要求，就说明可以这条路径可以被瓜分殆尽，是的$|path|-1$，但是这和$path$最小性矛盾。

但是为什么可以被瓜分呢？这里给出一种瓜分方案的构造方法。

设$pe$的路径为$a_0->a_1->a_2...->a_k$。

那么存在$x_0->a_0$，那么是不是意味着$x_0$的路径可以直接吞掉$pe$呢？错！$x_0$路径上的下一个点$x_1$说不定也被人指了。所以我们需要根据跳的步骤，构造一个影响方案，根据影响方案来吞掉$pe$。

根据我们跳的步骤构造影响方案：

这样就表示$x>>y$（如果存在多个$x$，随便选一个），但是由于$son[x]$跳的时候$y$还没有跳，所以这样构造出来的方案不可能存在$y^{\prime }>>son[x]$的情况。

注：下面瓜分$x$指的是将$x$以及$x$路径上$x$所能到达的点归到其他路径中去。

好，那么对于$x_0$，他是某条路径的终点，有一个点$y$，$x_0>>son[y]$，那么将$x_0$所在的路径延长，代替$son[y]$以及其下面的一段，然后将$y$变为终点，且路径数不变，那么对于$a_0$而言，对于$x_0>>a_0$，只需要在此之前先把$son[x_0]$瓜分了，然后让$x_0$连向$pe$即可。

按照上面的瓜分方法（即如果目前瓜分的是$x$，如果存在$y>>x$，则先瓜分$son[y]$，然后让$y$吞了$x$），不难证明$x$（跳点顺序中随便一个点）在不影响路径条数的情况下一定可以被瓜分，因为这样按照这样无限递增下去，接下来瓜分的点绝对不可能是$x$或者$x^{\prime }$，因为这样存在$x^{\prime }>>z$，但是由于递归下去的条件是存在$y>>son[x]$，即跳点顺序中$y$是在$x$前面的，所以后面瓜分递归中的点在跳点顺序中是不断往前跑的，而$x^{\prime }>>z$很明显违背了不存在$t_i>>t_j(i>j)$这条性质，所以瓜分递归中一定最后会跳掉一条路径的$ed$并停止递归，开始回溯。（当然，这里说的不影响路径条数仅当$x$不是路径起点的时候才不影响，否则条数会减一）

例子：

所以这样瓜分了$x_0$，就可以少一条路径啦。

得证。

代码

#include<cstdio>
#include<cstring>
#define  N  210
#define  M  41000
using  namespace  std;
struct  node
{int  y,next;
}a[M];int  len,last[N];
inline  void  ins(int  x,int  y){len++;a[len].y=y;a[len].next=last[x];last[x]=len;}
int  dis[N][N],n,m;
int  match[N];bool  v[N];
bool  check(int  x)
{v[x]=1;for(int  k=last[x];k;k=a[k].next){int  y=a[k].y;if(!match[y]  ||  (!v[match[y]]  &&  check(match[y])==1)){match[y]=x;return  1;}}return  0;
}
int  main()
{scanf("%d%d",&n,&m);for(int  i=1;i<=m;i++){int  x,y;scanf("%d%d",&x,&y);dis[x][y]=1;}for(int  i=1;i<=n;i++){for(int  j=1;j<=n;j++){for(int  k=1;k<=n;k++)if(dis[j][i]  &&  dis[i][k])dis[j][k]=1;}}for(int  i=1;i<=n;i++){for(int  j=1;j<=n;j++)if(dis[i][j])ins(i,j);}//传递闭包int  ans=0;for(int  i=1;i<=n;i++){memset(v,0,sizeof(v));ans+=check(i);}printf("%d\n",n-ans);return  0;
}

最后说

$>>$这个符号真正的意思其实是远大于的意思，但是这里为了方便重定义了这个符号，希望读者不要误解。