[二分图][匈牙利算法]SSL 1342 Machine Schedules

Description　　
　　我们现在有两台机器，A和B。 A机器有n个工作模式，分别为 mode_0、mode_1….mode_n-1，B机器有m个工作模式：mode_0、mode_1….mode_m-1，我们现在有一些工作，每个工作可以用一个三元组来描述(i,x, y )，表示这个工作的编号为i，它可以在A机器的mode_x下或B机器的mode_y模式下被完成。
　　我们现在有t个工作，去交给A、B两机器完成，机器如果改变一个模式需要人工去操作…
　　请你排出工作表，以使人工操作的次数最少。

题解

二分图。如果一项工作能被a机器x工作状态或b机器y工作状态解决的话，将x与y连边，这题便转换为了二分图的最小点覆盖问题了 
然后就直接码匈牙利算法

代码

#include<iostream>
#include<cstdio>
#include<memory.h>
using namespace std;
int n,m,k,f[101],q,x,y,ans;
bool map[101][101],visit[101];
bool xiongyalisuanfa(int a)
{
    int r;
    for (int i=1;i<=m;i++)
    if (map[a][i]&&!visit[i])
    {
        r=f[i];f[i]=a;visit[i]=1;
        if (r==0||xiongyalisuanfa(r)) return true;
        f[i]=r;
    }
    return false;
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for (int i=1;i<=k;i++)
    {
        scanf("%d%d%d",&q,&x,&y);
        map[x][y]=1;
    }
    for (int i=1;i<=n;i++)
    {
        memset(visit,0,sizeof(visit));
        if (xiongyalisuanfa(i)) ans++;
    }
    printf("%d",ans);
}