[cpp]
/*
題意：A機器有n(0~n-1)個模式，B機器有m(0~m-1)個模式
先有k個任務需要做，可以用A機器的ai模式做或者用B機器的bi模式做
任務無先後，換模式序重啟，開始兩個機器都在模式0
問最少需要重啟幾次
二分圖最小點覆蓋
A的模式為X集 B的模式為Y集
按任務建邊
求最小點覆蓋
任務是求最少的重啟次數，也就是最少要工作在幾個模式(除了0模式)
只要邊的任何一個端點被選中就行了
所以求最小點覆蓋 這些點抓住了所有的邊，集完成了所有任務，模式就是這個店所代表的模式
最小點覆蓋=二分圖最大匹配
*/
#include<stdio.h>
#include<vector>
using namespace std;
int n,m,k;
vector<int>v[201];
int vis[201];
int match[201];
int dfs(int i)
{
for(int j=0;j<v[i].size();++j)
{
if(!vis[v[i][j]+n])//+n是調整編號
{
vis[v[i][j]+n]=1;
if(match[v[i][j]+n]==-1||dfs(match[v[i][j]+n]))
{
match[v[i][j]+n]=i;
return 1;
}
}
}
return 0;
}
int main()
{
int i,a,b,c;
while(scanf("%d",&n),n)
{
scanf("%d%d",&m,&k);
for(i=0;i<=m+n;++i)
v[i].clear();
for(i=1;i<=k;++i)
{
scanf("%d%d%d",&a,&b,&c);
if(b&&c)
v[b].push_back(c);//只需要從X集指向Y集就好了 dfs()的時候就只是從X到Y
}
a=0;////匹配部分
memset(match,-1,sizeof(match));
for(i=1;i<=n;i++)
{
memset(vis,0,sizeof(vis));
if(dfs(i))
a++;
}////
printf("%d\n",a);
}
return 0;
}
作者：qq172108805
