Hdu 1150
Machine Schedule
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5379 Accepted Submission(s): 2664Problem DescriptionAs we all know, machine scheduling is a very classical problem in computer science and has been studied for a very long history. Scheduling problems differ widely in the nature of the constraints that must be satisfied and the type of schedule desired. Here we consider a 2-machine scheduling problem.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.
InputThe input file for this program consists of several configurations. The first line of one configuration contains three positive integers: n, m (n, m < 100) and k (k < 1000). The following k lines give the constrains of the k jobs, each line is a triple: i, x, y.The input will be terminated by a line containing a single zero.
OutputThe output should be one integer per line, which means the minimal times of restarting machine.Sample Input5 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
0Sample Output3
Accepted Code:
/*************************************************************************
> File Name: 1150.cpp
> Author: Stomach_ache
> Mail: sudaweitong@gmail.com
> Created Time: 2014年07月14日 星期一 14时21分28秒
> Propose:
************************************************************************/ #include <cmath>
#include <string>
#include <cstdio>
#include <fstream>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; int n, m, k;
int cx[], cy[], mark[];
int G[][]; int
path(int u) {
for (int v = ; v < m; v++) {
if (!mark[v] && G[u][v]) {
mark[v] = ;
if (cy[v] == - || path(cy[v])) {
cx[u] = v;
cy[v] = u;
return ;
}
}
}
return ;
} int
MaxMatch() {
memset(cx, -, sizeof(cx));
memset(cy, -, sizeof(cy));
int res = ;
for (int i = ; i < n; i++) {
if (cx[i] == -) {
memset(mark, , sizeof(mark));
res += path(i);
}
}
return res;
} int
main(void) {
while (~scanf("%d %d %d", &n, &m, &k) && n) {
memset(G, , sizeof(G));
for (int i = ; i < k; i++) {
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
if (b && c) G[b][c] = ;
}
printf("%d\n", MaxMatch());
} return ;
}
最新文章
- SharedPreferences漏洞, 无法避免,所以不要在里面存储敏感信息
- php文件类
- 关于C语言中的转义字符
- maketrans translate
- echart------属性详细介绍
- Project Management Process
- magento提速的一些小技巧,列举manegnto网站提速的
- ID选择器
- Delphi的IDHTTP的基本用法
- 四种方法解决DIV高度自适应问题
- vue-router2.0简单路由嵌套
- 如何使用Flexbox和CSS Grid,实现高效布局
- CLR设计类型之接口
- java 快速排序
- hadoop端口使用配置总结(非常好的总结)
- java~springboot~目录索引
- Chapter 5 Blood Type——4
- 利用Swashbuckle生成Web API Help Pages
- MySQL binlog group commit--commit stage
- VMXNET3 vs E1000E and E1000
热门文章
- Spring Boot配置公共的线程池
- Activiti配置实例以及Spring集成配置
- window环境下Python+OpenCV配置
- 数据库顶会VLDB论文解读:阿里数据库智能参数优化的创新与实践
- 3926: [Zjoi2015]诸神眷顾的幻想乡
- MYSQL中使用事务的案例
- 技术 | TypeScript
- 2019.10.30 csp-s模拟测试94 反思总结
- Leetcode437Path Sum III路径总和3
- Django项目:CRM(客户关系管理系统)--50--41PerfectCRM实现全局账号密码修改