Position:


List

Description

  我们知道机器调度是计算机科学中一个非常经典的问题。调度问题有很多种,具体条件不同,问题就不同。现在我们要处理的是两个机器的调度问题。

  有两个机器A和B。机器A有n种工作模式,我们称之为mode_0,mode_l,……,mode_n-1。同样,机器B有m种工作模式,我们称之为mode_0,mode_1,……,mode_m-1。初始时,两台机器的工作模式均为mode_0。现在有k个任务,每个工作都可以在两台机器中任意一台的特定的模式下被加工。例如,job0能在机器A的mode_3或机器B的mode_4下被加工,jobl能在机器A的mode_2或机器B的mode_4下被加工,等等。因此,对于任意的jobi,我们可以用三元组(i,x,y)来表示jobi在机器A的mode_x或机器B的mode_y下被加工。

  显然,要完成所有工作,我们需要不时的改变机器的工作模式。但是,改变机器的工作状态就必须重启机器,这是需要代价的。你的任务是,合理的分配任务给适当的机器,使机器的重启次数尽量少。

Input

第一行三个整数n,m(n,m<=100),k(k<6000)。接下来的k行,每行三个整数i,x,y。

Output

只一行一个整数,表示最少的重启次数。

Sample Input

 5 5 10

 0 1 1

 1 1 2

 2 1 3

 3 1 4

 4 2 1

 5 2 2

 6 2 3

 7 2 4

 8 3 3

 9 4 3

Sample Output

3

HINT

30%: n,m<30, k<100

100%: n,m<100,k<10000

Solution

二分图匹配直接上(Dinic||匈牙利)

Analysis:Konig 定理:最大匹配数 = 最小点覆盖数

注意开始机器是开着的,两边都为零,所以连的边都可以去掉

可恶的样例,居然没0,然后rank10->rank22,80分啊!

【Poj1325】Machine Schedule机器调度-LMLPHP

Code

// <machine.cpp> - Fri Sep 23 08:09:06 2016
// This file is made by YJinpeng,created by XuYike's black technology automatically.
// Copyright (C) 2016 ChangJun High School, Inc.
// I don't know what this program is. #include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define MOD 1000000007
#define INF 1e9
using namespace std;
typedef long long LL;
const int MAXN=210;
const int MAXM=100010;
inline int max(int &x,int &y) {return x>y?x:y;}
inline int min(int &x,int &y) {return x<y?x:y;}
inline int gi() {
register int w=0,q=0;register char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')q=1,ch=getchar();
while(ch>='0'&&ch<='9')w=w*10+ch-'0',ch=getchar();
return q?-w:w;
}
int n,match[MAXN];
vector<int>b[MAXN];bool f[MAXN];
inline void add(int v,int u){
if(!(v&&u))return;//这句话顶80分,坑~
b[u].push_back(v+n);b[v+n].push_back(u);
}
inline bool dfs(register int x){
if(f[x])return 0;
int num=b[x].size();f[x]=true;
for(int i=0;i<num;i++){
int nex=b[x][i];
if(match[nex]==-1||dfs(match[nex])){
match[x]=nex;match[nex]=x;return 1;
}
}
return 0;
}
int main()
{
freopen("machine.in","r",stdin);
freopen("machine.out","w",stdout);
while(n=gi(),n){
int ans=gi(),k=gi();
for(int i=0;i<=ans+n;i++)b[i].clear();
for(int i=1;i<=k;i++)ans=gi(),add(gi(),gi());
for(int i=0;i<MAXN;i++)match[i]=-1;ans=0;
for(int i=0;i<n;i++)
if(match[i]==-1){
memset(f,0,sizeof(f));
if(dfs(i))ans++;
}
printf("%d\n",ans);
}
return 0;
}
05-21 03:47