每个任务链接两台机器的两种模式,二分图,
每条边要选一个顶点,求最少的点,就是最小顶点覆盖问题
#include<stdio.h> #include<string.h> int map[101][101],link[101],mark[101],n,m; int find(int i) { int j; for(j=1;j<=m;j++) { if(map[i][j]==1&&mark[j]==0) { mark[j]=1; if(link[j]==0||find(link[j])==1) { link[j]=i; return 1; } } } return 0; } int main() { int i,sum,k,x,y,z; while(scanf("%d",&n),n) { scanf("%d%d",&m,&k); memset(map,0,sizeof(map)); memset(link,0,sizeof(link)); for(i=1;i<=k;i++) { scanf("%d%d%d",&x,&y,&z); map[y][z]=1; } sum=0; for(i=1;i<=n;i++) { memset(mark,0,sizeof(mark)); sum=sum+find(i); } printf("%d\n",sum); } return 0; }