首页 > 系统服务 > 详细

#二分图匹配#UVA1194 Machine Schedule

时间:2021-06-21 11:48:32      阅读:23      评论:0      收藏:0      [点我收藏+]

题目

有两台机器 \(A,B\) 分别有 \(n,m\) 种模式。

现在有 \(k\) 个任务。对于每个任务 \(i\) ,给定两个整数 \(a_i\)\(b_i\)?,

表示如果该任务在 \(A\) 上执行,需要设置模式为 \(a_i\)

如果该任务在 \(B\) 上执行,需要设置模式为 \(b_i\)

每台机器第一次开机默认处在0模式,且第一次开机不需要消耗时间。

任务可以以任意顺序被执行,但每台机器转换一次模式就要重启一次。

求怎样分配任务并合理安排顺序,能使机器重启次数最少。

\(1≤n,m≤100,1 \leq k \leq 1000,0 \leq a_i<n,0\leq b_i<m\)


分析

首先先把模式为0的任务去掉,然后考虑两种模式必选其一,
以下摘自《算法竞赛进阶指南》

  • 0要素:节点能分成独立的两个集合,每个集合内部有0条边
  • 1要素:每个节点只能与1条匹配边相连
  • 2要素:每条边有两个端点,二者至少选择一个(最小点覆盖)
    所以观察到这个模型为二分图最小点覆盖,直接求最大匹配即可

代码

#include <cstdio>
#include <cctype>
#define rr register
using namespace std;
const int N=201;
struct node{int y,next;}e[N*5];
int v[N],link[N],n,m,et,ans,upd,as[N];
inline signed iut(){
	rr int ans=0,f=1; rr char c=getchar();
	while (!isdigit(c)) f=(c==‘-‘)?-f:f,c=getchar();
	while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
	return ans*f;
}
inline void add(int x,int y){
	e[++et]=(node){y,as[x]},as[x]=et;
}
inline bool match(int x){
	for (rr int i=as[x];i;i=e[i].next)
	if (v[e[i].y]!=upd){
		v[e[i].y]=upd;
		rr int q=link[e[i].y];
		link[e[i].y]=x;
		if (!q||match(q)) return 1;
		link[e[i].y]=q;
	}
	return 0;
}
signed main(){
	while (n=iut()){
		m=iut(),et=ans=0;
		for (rr int Q=iut(),x,y;Q;--Q){
			iut(),x=iut(),y=iut();
			if (!x||!y) continue;
			add(x,y+n);
		}
		for (rr int i=1;i<=n;++i) ++upd,ans+=match(i);
		printf("%d\n",ans);
		for (rr int i=1;i<=n+m;++i) as[i]=link[i]=0;
	}
	return 0;
}

#二分图匹配#UVA1194 Machine Schedule

原文:https://www.cnblogs.com/Spare-No-Effort/p/14911735.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!