376. 机器任务 (二分图中,最小点覆盖 == 最大匹配数)
作者:
闪回
,
2024-04-08 20:18:00
,
所有人可见
,
阅读 2
//抽象模型能力很重要,在二分图中,最小点覆盖 == 最大匹配数
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 110;
bool g[N][N],st[N];
int match[N];
int n,m,k;
bool find(int x)
{
for(int i = 1;i<m;i++)
{
if(g[x][i] && !st[i])
{
st[i] = true;
int t = match[i];
if(t == 0 || find(t))
{
match[i] = x;
return true;
}
}
}
return false;
}
int main()
{
while(cin>>n,n)
{
memset(g,0,sizeof g);
memset(match,0,sizeof match);
int res = 0;
cin>>m>>k;
while(k--)
{
int i,a,b;
cin>>i>>a>>b;
if(!a || !b)continue;
g[a][b] = true;
}
for(int i = 1;i<n;i++)
{
memset(st, 0, sizeof st);
if(find(i))res++;
}
cout<<res<<endl;
}
return 0;
}