题解 UVA1194 【Machine Schedule】
逃离地球
2019-09-14 00:55:23
[题目链接](https://www.luogu.org/problem/UVA1194)
把机器A的n个模式作为n个左部节点，机器B的m个模式作为m个右部节点，每个任务是一条边，连接a[i]和b[i]。由于每个任务需要在A和B之间选一个，所以求这个二分图的最小点覆盖就相当于用最少的模式完成任务。
由König定理，二分图最小点覆盖包含的点数等于二分图最大匹配包含的边数。所以只需求那张图的最大匹配即可。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int INF=10e8;
#define FOR(i,m,n) for (register int i = m; i <= n; i++)
#define _FOR(i,m,n) for (register int i = m ; i >= n; i--)
#define QAQ printf("QAQ\n");
int n,m,e,Map[1001][1001],match[1001]={0},vis[1001];
bool dfs(int x){
for(int i=1;i<=m;i++){
if(Map[x][i]&&!vis[i]){
vis[i]=1;
if(!match[i]||dfs(match[i])){
match[i]=x;
return true;
}
}
}
return false;
}//匈牙利
int main() {
while(1){
cin>>n;
if(n==0)
break;
cin>>m>>e;
int x,y,jntm;
memset(Map,0,sizeof(Map));
memset(match,0,sizeof(match));
for(int i=0;i<e;i++){
cin>>jntm>>x>>y;//输入的第一个数毫无作用
if(x==0||y==0){
continue;
}
Map[x][y]=1;
}
int cnt=0;
for(int i=1;i<=n;i++){
memset(vis,0,sizeof(vis));
cnt+=dfs(i);//求最大匹配
}
cout<<cnt<<endl;
}
return 0;
}
```