这题与以前的代码没什么两样,就是多算一个“最小路径覆盖数=总的顶点数-最大匹配数。把原图一个顶点分成两个集合。
代码如下:
#include<stdio.h> #include<string.h> int n; int map[125][125]; int match[125],used[125]; int find(int i) { for(int j=1;j<=n;j++) { if(map[i][j]&&!used[j]) { used[j]=1; if(match[j]==0||find(match[j])) { match[j]=i; return 1; } } } return 0; } int main() { int t,m,x,y; scanf("%d",&t); while(t--) { memset(map,0,sizeof(map)); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); map[x][y]=1; } memset(match,0,sizeof(match)); int sum=0; for(int i=1;i<=n;i++) { memset(used,0,sizeof(used)); if(find(i)) sum++; } printf("%d\n",n-sum); } return 0; }