UVA1194 Machine Schedule 题解

Link

UVA1194 Machine Schedule

Solve

比较经典的最小覆盖模型，二分图最小覆盖的模型特点是每条边有两个端点，二者至少选其一。

这道题目，每个任务要么在机器(A)上以(a[i])执行，要么在机器(B)上以(b[i])执行，二者必选其一，因此，我们可以把机器(A)的(M)种模式作为(M)种左端点，机器(B)中的(M)种作为(M)个右端点，每个任务作为无向边，链接左部的第(a[i])个节点与右部的第(b[i])个节点。

这张图显然是个二分图，求出它的最小覆盖就等价于用最少的模式来执行所有任务，时间复杂度为(O(NM))

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=10005,maxe=20005;
int N,M,K,vis[maxn],nxt[maxe],cnt,match[maxn],son[maxe],lnk[maxn],ans;
inline int read(){
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}
void add_e(int x,int y){son[++cnt]=y;nxt[cnt]=lnk[x];lnk[x]=cnt;} 
bool DFS(int x){
	for(int j=lnk[x];j;j=nxt[j]){
		if(!vis[son[j]]){
			vis[son[j]]=1;
			if(!match[son[j]]||DFS(match[son[j]])){
				match[son[j]]=x;
				return true;
			}
		}
	}
	return false;
}
int main(){
	freopen("UVA1194.in","r",stdin);
	freopen("UVA1194.out","w",stdout);
	while(true){
		N=read();if(!N)break;
		M=read();K=read();
		memset(lnk,0,sizeof lnk);
		memset(son,0,sizeof son);
		memset(nxt,0,sizeof nxt);
		memset(match,0,sizeof match);
		cnt=0;
		for(int i=1;i<=K;i++){
			read();int x=read(),y=read();
			if(!x||!y)continue;
			add_e(x,y+N);
			add_e(y+N,x);
		}
		ans=0;
		for(int i=0;i<N;i++){
			memset(vis,0,sizeof vis);
			if(DFS(i))ans++;
		}
		printf("%d
",ans);
	}
	return 0;
}