分析:二分匹配,二分图最小路径覆盖=点的个数-最大匹配
#include <iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<string> #define maxn 125 using namespace std; int n,m,w[maxn][maxn]; int linker[maxn]; bool used[maxn]; bool dfs(int u) { int v; for(v=1;v<=n;v++) if(w[u][v]&&!used[v]) { used[v]=true; if(linker[v]==-1||dfs(linker[v])) { linker[v]=u; return true; } } return false; } int hungary() { int res=0; int u=0; memset(linker,-1,sizeof(linker)); for(u=1;u<=n;u++) { memset(used,0,sizeof(used)); if(dfs(u)) res++; } return res; } int main() { int t,k,i,j,tmp; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&k); memset(w,0,sizeof(w)); while(k--) { scanf("%d%d",&i,&j); w[i][j]=1; } printf("%d\n",n-hungary()); } return 0; }