很明显求最小路径覆盖
就是求最大匹配
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn=;
vector<int> map[maxn];
int vis[maxn];
int link[maxn];
int n,k;
bool dfs(int t)
{
int i,x,size=map[t].size();
for(i=;i<size;++i)
{
x=map[t][i];
if(!vis[x])
{
vis[x]=;
if(link[x]==-||dfs(link[x]))
{
link[x]=t;
return ;
}
}
}
return ;
}
int main()
{
int i,a,b,ans,t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&k);
for(i=;i<=n;++i) map[i].clear();
for(i=;i<=k;++i)
{
scanf("%d%d",&a,&b);
map[a].push_back(b);
}
memset(link,-,sizeof(link));
ans=;
for(i=;i<=n;++i)
{
memset(vis,,sizeof(vis));
if(dfs(i)) ans++;
}
printf("%d\n",n-ans);
}
}