HDU [P1150] Machine Schedule

二分图匹配求最小点覆盖

把两个机器作为两个集合,把每个任务当做边建图.那么所求的就是二分图的最小点覆盖.

但是最开始WA了,原因在于,题目要求的是变换的次数,也就是与0连的边需要删去.

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

int init(){

	int rv=0,fh=1;

	char c=getchar();

	while(c<'0'||c>'9'){

		if(c=='-') fh=-1;

		c=getchar();

	}

	while(c>='0'&&c<='9'){

		rv=(rv<<1)+(rv<<3)+c-'0';

		c=getchar();

	}

	return fh*rv;

}

int n,m,k,g[105][105],match[105];

bool f[105];

bool hungarian(int u){

	for(int i=1;i<=g[u][0];i++){

		int v=g[u][i];

		if(!f[v]){

			f[v]=1;

			if(match[v]==-1||hungarian(match[v])){

				match[v]=u;

				return 1;

			}

		}

	}

	return 0;

}

int main(){

	while(1){

		n=init();

		if(!n) break;

		m=init();k=init();

		memset(g,0,sizeof(g));

		for(int i=0;i<=n;i++) match[i]=-1;

		for(int i=1;i<=k;i++){

			int t=init(), u=init(),v=init();

			if(u&&v) g[u][++g[u][0]]=v;

		}

		int ans=0;

		for(int i=1;i<n;i++){

			memset(f,0,sizeof(f));

			if(hungarian(i)) ans++;

		}

		cout<<ans<<endl;

	}

	return 0;

}

巴特西

HDU [P1150] Machine Schedule

二分图匹配求最小点覆盖

最新文章

热门文章