捉迷藏（二分图，最小路径重复覆盖）

路径重复覆盖）"/>

捉迷藏（二分图，最小路径重复覆盖）

最小路径覆盖：用最少互不相交的路径，将点全部覆盖。

最小路径重复覆盖：用最少多少条路径覆盖所有点，路径可以有公共点和公共边。

在二分图中:最小路径覆盖=总点数-最大匹配数。在DAG图G中的最小路径重复覆盖==在他的传递闭包图G’中的最小路径覆盖。

代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define SIS std::ios::sync_with_stdio(false)
#define space putchar(' ')
#define enter putchar('\n')
#define lson root<<1
#define rson root<<1|1
typedef pair<int,int> PII;
typedef pair<int,PII> PIII;
const int mod=100003;
const int N=1e5+5;
const int inf=0x7f7f7f7f;int gcd(int a,int b)
{return b==0?a:gcd(b,a%b);
}ll lcm(ll a,ll b)
{return a*(b/gcd(a,b));
}template <class T>
void read(T &x)
{char c;bool op = 0;while(c = getchar(), c < '0' || c > '9')if(c == '-')op = 1;x = c - '0';while(c = getchar(), c >= '0' && c <= '9')x = x * 10 + c - '0';if(op)x = -x;
}
template <class T>
void write(T x)
{if(x < 0)x = -x, putchar('-');if(x >= 10)write(x / 10);putchar('0' + x % 10);
}
ll qsm(int a,int b,int p)
{ll res=1%p;while(b){if(b&1)res=res*a%p;a=1ll*a*a%p;b>>=1;}return res;
}int head[N],nex[N],to[N];
int n,m;
int color[N];
int g[205][205];
int match[205];
int vis[205];bool fnd(int x)
{for(int i=1;i<=n;i++){if(!vis[i]&&g[x][i]){vis[i]=1;int t=match[i];if(t==0||fnd(t)){match[i]=x;return true;}}}return false;
}
int main()
{scanf("%d%d",&n,&m);while(m--){int a,b;scanf("%d%d",&a,&b);g[a][b]=1;}for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(g[i][k]&&g[k][j]) g[i][j]=1;int res=0;for(int i=1;i<=n;i++){memset(vis,0,sizeof vis);if(fnd(i)) res++;}printf("%d\n",n-res);return 0;}