求最小路径覆盖Orz
code:
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,m,link[125]; bool map[125][125],vis[125]; bool find(int x) { int y; for(y=1;y<=n;y++) { if(map[x][y] && !vis[y]) { vis[y]=1; if(!link[y] || find(link[y]) ) { link[y]=x; return true; } } } return false; } int solve() { int x,ans=0; for(x=1;x<=n;x++) { memset(vis,0,sizeof(vis)); if(find(x)) ans++; } return n-ans; } int main() { int cas,i,k,a,b; scanf("%d",&cas); for(k=1;k<=cas;k++) { memset(map,0,sizeof(map)); memset(link,0,sizeof(link)); scanf("%d%d",&n,&m); for(i=1;i<=m;i++) { scanf("%d%d",&a,&b); map[a][b]=1; } printf("%d\n",solve()); } return 0; }