将A和B分为2分图的两边,对于每个工作(i,x,y),就在两个点上连一条边,这条边就是工作,这样问题就转化成了用最少的点覆盖所有的边,即二分图的最小点覆盖。
code:
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int MAXN = 110; int n,m,k; bool graph[MAXN][MAXN]; bool vis[MAXN]; int link[MAXN]; int find(int x) { int y; for(y=1;y<=m;y++) { if(graph[x][y] && !vis[y]) { vis[y]=true; if(link[y]==0 || find(link[y])) { link[y]=x; return true; } } } return false; } int main() { int i,j,a,b,c,ans; while(~scanf("%d",&n)&&n) { scanf("%d%d",&m,&k); ans=0; memset(link,0,sizeof(link)); memset(graph,0,sizeof(graph)); for(i=1;i<=k;i++) { scanf("%d%d%d",&a,&b,&c); graph[b][c]=1; } for(i=1;i<=n;i++) { memset(vis,0,sizeof(vis)); if(find(i)) ans++; } printf("%d\n",ans); } return 0; }