Machine Schedule 题解

题目链接

把机器A的n个模式作为n个左部节点，机器B的m个模式作为m个右部节点，每个任务是一条边，连接a[i]和b[i]。由于每个任务需要在A和B之间选一个，所以求这个二分图的最小点覆盖就相当于用最少的模式完成任务。

由König定理，二分图最小点覆盖包含的点数等于二分图最大匹配包含的边数。所以只需求那张图的最大匹配即可。

代码：

#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;
}