HDU 1151Air Raid 最小路径覆盖=n-最大匹配量 （第二道二分匹配）
#include<iostream>#include<stdio.h>#include<math.h>#include<string.h>#include<stdlib.h>#include<algorithm>using namespace std;int map[125][125],ve[125],vs[125];int s,e;int getpath(int u){ int i; for(i=1;i<=s;i++) { if(!map[u][i] || ve[i]) continue; ve[i]=1; if(!vs[i] || getpath(vs[i])) { vs[i]=u; return 1; } } return 0;}int main(){// freopen("in.txt","r",stdin); int i,a,b,t; scanf("%d",&t); while(t--) { memset(map,0,sizeof(map)); memset(vs,0,sizeof(vs)); scanf("%d%d",&s,&e); for(i=0;i<e;i++) { scanf("%d%d",&a,&b); map[a][b]=1; } int ans=0; for(i=1;i<=s;i++) { memset(ve,0,sizeof(ve)); ans+=getpath(i); } printf("%d\n",s-ans); } return 0;}
