伞兵天降 最小路径覆盖

真实顶点数-最大匹配数

#include <bits/stdc++.h>
using namespace std;
int a,b;
int idx=0;int h[125];int visited[125];int match[125];
struct node
{int v,n;
}e[1445];
void add(int u,int v)
{e[++idx]={v,h[u]};h[u]=idx;
}
int dfs(int u)
{for(int i=h[u];i;i=e[i].n){int v=e[i].v;if(visited[v]) continue;visited[v]=1;if(!match[v]||dfs(match[v])){match[v]=u;return 1;}}return 0;
}
int main()
{int n;cin>>n;while(n--){idx=0;cin>>a>>b;memset(h,0,sizeof(h));memset(match,0,sizeof(match));while(b--){int uu,vv;cin>>uu>>vv;add(uu,vv);}int ans=0;for(int i=1;i<=a;i++){memset(visited,0,sizeof(visited));if(dfs(i)) ans++;}cout<<a-ans<<endl;}}