HDU - 1150 POJ - 1325 Machine Schedule 匈牙利算法(最小点覆盖)
Machine Schedule
There are two machines A and B. Machine A has n kinds of working modes, which is called mode_0, mode_1, ..., mode_n-1, likewise machine B has m kinds of working modes, mode_0, mode_1, ... , mode_m-1. At the beginning they are both work at mode_0.
For k jobs given, each of them can be processed in either one of the two machines in particular mode. For example, job 0 can either be processed in machine A at mode_3 or in machine B at mode_4, job 1 can either be processed in machine A at mode_2 or in machine B at mode_4, and so on. Thus, for job i, the constraint can be represent as a triple (i, x, y), which means it can be processed either in machine A at mode_x, or in machine B at mode_y.
Obviously, to accomplish all the jobs, we need to change the machine's working mode from time to time, but unfortunately, the machine's working mode can only be changed by restarting it manually. By changing the sequence of the jobs and assigning each job to a suitable machine, please write a program to minimize the times of restarting machines.
Input
The input will be terminated by a line containing a single zero.
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
0
Sample Output
3
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<math.h>
#include<queue>
#include<set>
#include<stack>
#include<algorithm>
#include<vector>
#include<iterator>
#define MAX 1005
#define INF 0x3f3f3f3f
#define MOD 1000000007
using namespace std; typedef long long ll;
int n,m;
int line[MAX][MAX],used[MAX],mm[MAX];
int find(int x){
int i,j;
for(j=;j<=m;j++){
if(line[x][j]&&!used[j]){
used[j]=;
if(!mm[j]||find(mm[j])){
mm[j]=x;
return ;
}
}
}
return ;
}
int main()
{
int xx,x,y,k,i;
while(scanf("%d",&n)&&n>){
scanf("%d%d",&m,&k);
memset(line,,sizeof(line));
memset(mm,,sizeof(mm));
for(i=;i<=k;i++){
scanf("%d%d%d",&xx,&x,&y);
if(x>&&y>){
line[x][y]=;
}
}
int c=;
for(i=;i<=n;i++){
memset(used,,sizeof(used));
if(find(i)) c++;
}
printf("%d\n",c);
}
return ;
}
最新文章
- 文件权限:普通(r、w、x)和特殊(s、t)
- 【转】File类应用 - FilenameFilter 和 FileFilter
- XML代码生成器——XMLFACTORY 简介(一)
- Azure Redis Cache (1) 入门
- Android无线调试
- Linux高级编程--06.进程概述
- mvc 简单笔记
- ubuntu 命令学习大全
- 怎么做QQ、微信等消息气泡
- checkbox美化;给div加上checked属性
- [搜片神器]BT种子下载超时很多的问题分析
- 如何重载浏览器 onload 事件后加载的资源文件
- make: *** No rule to make target `out
- 在Delphi中使用C++对象(转)
- 课后练习:C语言实现Linux命令——od
- MyBatis - 10.MyBatis扩展
- NOIP2012借教室
- EZ 2018 06 24 NOIP2018 模拟赛(二十)
- Python 将图片转化为 HTML 页面
- xmtech-3516默认环境变量
热门文章
- Notepad++ QuickText 插件的 HTML 配置: \Notepad++\plugins\Config\QuickText.ini
- Cannot run program “git.exe”: createprocess error=2,系统找不到指定的文件
- Ceph集群rbd-mirror A、B区域备份实施方案
- 超限学习机 (Extreme Learning Machine, ELM) 学习笔记 (一)
- A Pangram
- Python运维编程
- tkinter之button
- JS判断数字、中文、小数位数
- IDEAL葵花宝典:java代码开发规范插件 checkstyle、visualVM、PMD 插件
- struts2 validate手动验证