博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
poj 3216 Repairing Company
阅读量:6435 次
发布时间:2019-06-23

本文共 2242 字,大约阅读时间需要 7 分钟。

Repairing Company
Time Limit: 1000MS   Memory Limit: 131072K
Total Submissions: 5915   Accepted: 1599

Description

Lily runs a repairing company that services the Q blocks in the city. One day the company receives M repair tasks, the ith of which occurs in block pi, has a deadline ti on any repairman’s arrival, which is also its starting time, and takes a single repairman di time to finish. Repairmen work alone on all tasks and must finish one task before moving on to another. With a map of the city in hand, Lily want to know the minimum number of repairmen that have to be assign to this day’s tasks.

Input

The input contains multiple test cases. Each test case begins with a line containing Q and M (0 < Q ≤ 20, 0 < M ≤ 200). Then follow Q lines each with Q integers, which represent a Q ×Q matrix Δ = {δij}, where δij means a bidirectional road connects the ith and the jth blocks and requires δij time to go from one end to another. If δij = −1, such a road does not exist. The matrix is symmetric and all its diagonal elements are zeroes. Right below the matrix are M lines describing the repairing tasks. The ith of these lines contains pi, ti and di. Two zeroes on a separate line come after the last test case.

Output

For each test case output one line containing the minimum number of repairmen that have to be assigned.

Sample Input

1 201 1 101 5 100 0

Sample Output

2

Source

, crazyb0y
1 //336K    94MS    C++    1520B    2013-11-09 10:52:29 2 /* 3      4     题意: 5         一家维修公司,服务的 Q 街区。每个街区有一定距离, 6     一天公司收到M修理任务,第i个任务发生在第i个街区,并且 7     每个任务都有起始时间 ti,完成一个任务需要di时间.修理工 8     必须完成一个任务后,再去另一个.问要完成这M个任务最少 9     需要多少个修理工? 10     11     最短路+二分图匹配:12         这题的要点在于想到用二分图的做法和构图。首先由于13     修理任务和修理工是两个集合,所以可使用二分图。然后构图14     的时候先用floyd算法(数据<=20)求出每个街区Q间的最短路,15     然后比较建图:若第j个街区任务的开始时间大于等于第i个16     街区的任务完成时间 + 路上花费时间 则i到j间连一条边17         18     本题求的是最小路径覆盖,使用匈牙利模板可得19         20         最小路径覆盖 = 节点数m - 最大匹配数  21     22 */23 #include
24 #include
25 #define inf 0x7ffffff26 struct node{27 int p,t,d;28 }M[205];29 int map[25][25];30 int g[205][205];31 int match[205];32 int vis[205];33 int n,m;34 int Min(int a,int b)35 {36 return a

 

转载于:https://www.cnblogs.com/GO-NO-1/articles/3415416.html

你可能感兴趣的文章
[爱上统计学]-[笔记]-计算和理解平均数
查看>>
mongoDB 3.0以前版本 - 入门指南、示例
查看>>
Win7下RicohC4500打印机无法打印的问题
查看>>
android中RelativeLayout无法填充ScrollView布局的问题
查看>>
通过Git WebHooks+脚本实现自动更新发布代码
查看>>
OGNL报错:Exception in thread "main" java.lang.ExceptionInInitializerError
查看>>
iptables 限制网速
查看>>
把Windows 2000 Server的域控制器迁移到Windows Server 2003域控制器的具体操作步骤
查看>>
撰写oracle-sql-hint的注意事项
查看>>
mongdb集群3.4 shard 模式
查看>>
vCloud Automation Center (vCAC) 6.0 (二)
查看>>
apache和tomcat的区别
查看>>
Exchange 2007 中特殊应用解析
查看>>
js向jsp传中文出现乱码的解决方法
查看>>
如何改变系统收藏夹的位置
查看>>
使用TiledLayer类及Canvas类实现游戏背景图层
查看>>
高效网管 行业信息化发展大势所趋——唐山供电公司营销部
查看>>
Exchange2010 Outlook自动发现
查看>>
pandas.read_csv
查看>>
ado.net连接池
查看>>