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
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 #include24 #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