POJ 1325 Machine Schedule(二分图匹配)

题目大意：有两个机器A和B，A机器有n个模式，B机器有m个模式,两个机器最初在0模式
然后有k个作业，每个作业有三个参数i，a，b
i代表作业编号，a和b代表第i作业要么在A机器的a模式下完成【或者】在B机器的b模式下完成
问两个机器总共最少变换多少次可以完成所有作业
解题思路：很水的一个二分图的最小点覆盖
建立一个二分图，左边代表A机器，有n个点，代表有n个模式
右边代表B机器，有m个点，代表有m个模式
现在对于每个作业，i,a,b都使左边a点指向右边b点即可
这样如果我们要把所有的作业做完，是不是找出最小的点覆盖将所有的边都覆盖掉即可
然后最小点覆盖等于最大匹配，用匈牙利直接过
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
using namespace std;
#define maxn 1005
int nx;
int ny;
int jobnum;
int g[maxn][maxn];
int ans;
int sx[maxn],sy[maxn];
int cx[maxn],cy[maxn];
int path(int u)
{
sx[u]=1;
int v;
for(v=1;v<=ny;v++)
{
if((g[u][v]>=0)&&(!sy[v]))
{
sy[v]=1;
if(!cy[v]||path(cy[v]))
{
cx[u]=v;
cy[v]=u;
return 1;
}
}
}
return 0;
}
int solve()
{
ans=0;
int i;
memset(cx,0,sizeof(cx));
memset(cy,0,sizeof(cy));
for(i=1;i<=nx;i++)
{
if(!cx[i])
{
memset(sx,0,sizeof(sx));
memset(sy,0,sizeof(sy));
ans+=path(i);
}
}
return 0;
}


int main()
{
int i,j,k,m;
while(scanf("%d",&nx))
{
if(nx==0)
break;
scanf("%d%d",&ny,&jobnum);
memset(g,-1,sizeof(g));
for(k=0;k<jobnum;k++)
{
scanf("%d%d%d",&m,&i,&j);
g[i][j]=m;
}
solve();
printf("%d\n",ans);
}
return 0;
}