2016微软探星 | Part-Time Jobs
这是此次在线笔试的最后一题，也是难度最大的一题。主要考查图的最短路径，动态规划等知识。
在做这道题的过程中经历了无数次TLE(运行超时)才最终通过，最后发现要通过此题，必须所有耗时运算都考虑到，并且尽可能优化。真是每一环都不能有失，好在不是限时做题，不断优化代码😄。
题目：
时间限制:20000ms
单点时限:2000ms
内存限制:512MB
描述
Little Hu is taking paid part-time jobs in his college. There are N
buildings in his college, numbered from 1 to N. These buildings are connected by M bi-directional paths in such a way that every pair of buildings is connected by these paths directly or indirectly. Moving from one building to another will cost Little Hu some time.
In the morning Little Hu receives Q jobs. Each job can be described with 5 integers, Li, Si, Ei, Ti, Ci. Li, the building number of the i-th job, describes the location to do the job. Si is the earliest time to start the job and Ei is the latest time to start the job. Ti is the time cost. Ci is the amount of money paid if Little Hu finished the job on time.
Little Hu starts at time 0 in building 1. He wants to maximize his total pay by carefully selecting jobs. Can you write a program to help him find the maximum total pay?
输入
The first line contains 3 integers N, M and Q.
The following M lines describe the paths. Each line contains 3 integers Ui, Vi and Wi indicating that there is path between building Ui and Vi and moving from Ui to Vi along the path, or vice versa, costs time Wi.
The following Q lines describe the jobs. Each line contains 5 integers Li, Si, Ei, Ti, Ci.
For 20% of the data: 1 ≤ Ui, Vi, Li ≤ N ≤ 5, 1 ≤ M ≤ 20, 1 ≤ Q ≤ 5
For 40% of the data: 1 ≤ Ui, Vi, Li ≤ N ≤ 100, 1 ≤ M ≤ 1000, 1 ≤ Q ≤ 10
For 100% of the data: 1 ≤ Ui, Vi, Li ≤ N ≤ 10000, 1 ≤ M ≤ 1000000, 1 ≤ Q ≤ 20
For 100% of the data: 0 ≤ Si ≤ Ei ≤ 10000, 1 ≤ Ti, Wi ≤ 10000, 1 ≤ Ci ≤ 100, Ui ≠ Vi
输出
Output the maximum pay Little Hu can get.
样例输入
3 5 5
3 1 4
3 2 2
1 2 5
1 3 2
3 1 4
3 5 9 3 8
1 4 7 4 4
3 7 10 4 8
2 2 3 4 9
3 3 15 4 8
样例输出
24
解释：
小H在学校里面做兼职，学校里有N个大楼，有的大楼之间有双向通道可以直达这里开始做题的时候没注意导致出错，以为是单向路径，其实应该是1->3耗时2的话，那么3->1也是2，一共有M条路径。
一天早上小H收到Q份工作，每份工作都有地点L、最早开始时间S、最晚开始时间E、耗时T、收入C。
现在小H从0小时开始，位置1的大楼出发。那么他怎么安排获取的工作才能获得最大收入？
结果输出最大收入。
分析：
1、首先看到这题有地点与路径，还有移动耗时，那么肯定需要把输入的点与点的最短路径求到，后面求收入的时候才能知道工作转移最少耗时，从而最大化收入。
我在求最短路的时候，最开始用的是Floyd最短路算法，而且图是用矩阵保存，最后提交发现仅仅计算最短路就花去了10000多ms。
最后仔细看题，发现此题路径相对于点的关系来说很少，是个稀疏图，应该用邻接表存储，最短路也换成了dijkstra优先队列算法。提交发现单点的最短路耗时下来了，但是求10000个点的最短路肯定还是会超时。但其实工作最多只有20个，其实我们应该求到每个工作转移之间的最短耗时就行了。
最短路网上很多实现方法，我也是找的一个源码直接用，就不详述了。
2、有了最短路，接下来就是计算怎么安排工作顺序得到最大收入。我的思路是：分别从每个工作开始，做完了接下来做其他工作，迭代找每个最大的子工作顺序，返回去得到最大输出。例如有3份工作，那么有下图这样的查找顺序：
Job.png
从工作0开始，找工作1，2，3为起点的最大收入，然后分别递归着子起点最大收入，最后就可以得到最大收入。每次迭代带上当前路径访问过的工作、当前位置、耗用时间等信息。代码如下：
int maxPay(int index, bool *flag, int pastTime, int currentLoc)
{
if (jvec[index].end < pastTime + matDis[currentLoc][index]) {
return 0;
}
bool temp[25];
for (int i = 0; i < 25; i++) {
temp[i] = flag[i];
}
temp[index] = true;
int value = jvec[index].value;
int maxV = 0;
if (matDis[currentLoc][index] + pastTime > jvec[index].start) {
pastTime += matDis[currentLoc][index] + jvec[index].time;
}
else
{
pastTime = jvec[index].start + jvec[index].time;
}
currentLoc = index;
for (int i = 1; i < jvec.size(); i++) {
if (!temp[i] && jvec[i].end >= pastTime + matDis[currentLoc][i]) {
// temp[i] = true;
maxV = max(maxV,maxPay(i,temp,pastTime,currentLoc));
}
}
return value + maxV;
}
最后提交后结果：
这里是已经用了dijkstra优化最短路解法的代码，还是超时😭。
分析一下其实可以看出，这段代码需要运行N！次，假如有20个工作，那么第一层调用是20，第二层是19，依次类推就是20＊19＊18...＊1。是很大的一个数字，我在本地机子上模拟了下面的输入：
3 5 20
3 1 4
3 2 2
1 2 5
1 3 2
3 1 4
1 1 100 1 9
1 1 100 1 9
1 1 100 1 9
1 1 100 1 9
1 1 100 1 9
1 1 100 1 9
1 1 100 1 9
1 1 100 1 9
1 1 100 1 9
1 1 100 1 9
1 1 100 1 9
1 1 100 1 9
1 1 100 1 9
1 1 100 1 9
1 1 100 1 9
1 1 100 1 9
1 1 100 1 9
1 1 100 1 9
1 1 100 1 9
1 1 100 1 9
20个工作都是一样，而且保证都可以完成，输出肯定应该是20＊9=180。用上面的代码就会一直调用，很久才输出，可以看出提交判定超时是必然的。
有了上面的思路，其实考虑压缩一下循环应该就行了。仔细思考一下，其实走到第二层迭代的时候，完成工作顺序1->2与2->1其实输出的value是一样的，我们可以把他们记录成一个值（1，2），记录最小耗时、位置等信息，然后到第三层，是1->2->3还是2->1->3，都应该是（1，2）->3。如图：
Job Pair.png
这要做，我们得到最大值的循环查找次数就会变成2^N这个量级，最大N＝20也只有1e6左右，而刚才的方法是1e18左右。
实现代码如下：
int loopMaxPay()
{
queue<pair<int,int>> jobQueue; // <jobPair,location>
queue<int> valueQueue;
map<int,int> pairMap; // <jobPair,leastTime>
// for (int i = 1; i < pow(2, jvec.size()); i++) {
// for (int j = 1; j < jvec.size(); j++) {
// pastTime[i][j] = INT_MAX / 2;
// }
// }
fill(pastTime[0], pastTime[(int)pow(2, jvec.size()) + 1]+20, INT_MAX / 2);
pastTime[0][0] = 0;
jobQueue.push(make_pair(0, 0));
valueQueue.push(0);
int maxValue = 0;
while (!jobQueue.empty()) {
pair<int, int> temp = jobQueue.front();
int value = valueQueue.front();
maxValue = max(value,maxValue);
jobQueue.pop();
valueQueue.pop();
for (int i = 1; i < jvec.size(); i++) {
Job tempJob = jvec[i];
if (!((int)pow(2, i) & temp.first)) { // not in pair
int start = max(tempJob.start, pastTime[temp.first][temp.second] + matDis[temp.second][i]);
if (start <= tempJob.end) {
pair<int, int> newPair = make_pair((int)pow(2, i) + temp.first, i);
if (pastTime[newPair.first][i] > start + tempJob.time) {
pastTime[newPair.first][i] = start + tempJob.time;
if (!flag[newPair.first][i]) {
flag[newPair.first][i] = true;
jobQueue.push(newPair);
valueQueue.push(value + tempJob.value);
}
}
}
}
}
}
return maxValue;
}
这里对于（1，2）这种合并工作的记录与判断是否包含在集合里用到了位方法，（1，2）记录为21+22 ＝ 6，二进制就是110。对于3是否包含在记录里，用2^3 & 6判断，也就是1000&110，结果肯定是0。
但上面代码提交还是超时，一个是因为其实对与(1，2)记录可以用3，也就是20+21来记录，这样前面填充最大值就可以少很多操作。还有就是用移位运算代替pow运算。
其实整体算法思路已经是正确了，就是一些耗时操作需要调优，开始我是用map来记录组合的最短时间，发现耗时，最后用数组来实现了。
完整通过代码如下：
//
// main.cpp
// Part-Time Jobs
//
// Created by Jiao Liu on 8/11/16.
// Copyright © 2016 ChangHong. All rights reserved.
//
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <queue>
#include <limits.h>
#include <map>
#include <math.h>
using namespace std;
vector<pair<int,int> > G[10005];
int N;
int pastTime[2100000][21];
bool flag[2100000][21];
struct Job {
int loc,start,end,time,value;
};
vector<Job> jvec;
int matDis[25][25];
int dis[10005];
void dij(int x){
fill(dis,dis+N+1,INT_MAX/2);
dis[x]=0;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
q.push(make_pair(0,x));
while(!q.empty()){
pair<int,int> tx=q.top();q.pop();
if(tx.first!=dis[tx.second])continue;
int p=tx.second;
for(int i=0;i<G[p].size();++i){
pair<int,int> edge=G[p][i];
int y=edge.first,w=edge.second;
if(dis[y]>dis[p]+w){
dis[y]=dis[p]+w;
q.push(make_pair(dis[y],y));
}
}
}
}
int maxPay(int index, bool *flag, int pastTime, int currentLoc)
{
if (jvec[index].end < pastTime + matDis[currentLoc][index]) {
return 0;
}
bool temp[25];
for (int i = 0; i < 25; i++) {
temp[i] = flag[i];
}
temp[index] = true;
int value = jvec[index].value;
int maxV = 0;
if (matDis[currentLoc][index] + pastTime > jvec[index].start) {
pastTime += matDis[currentLoc][index] + jvec[index].time;
}
else
{
pastTime = jvec[index].start + jvec[index].time;
}
currentLoc = index;
for (int i = 1; i < jvec.size(); i++) {
if (!temp[i] && jvec[i].end >= pastTime + matDis[currentLoc][i]) {
// temp[i] = true;
maxV = max(maxV,maxPay(i,temp,pastTime,currentLoc));
}
}
return value + maxV;
}
int loopMaxPay()
{
queue<pair<int, int>> jobQueue; // <jobPair,location>
queue<int> valueQueue;
// for (int i = 1; i < pow(2, jvec.size()); i++) {
// for (int j = 1; j < jvec.size(); j++) {
// pastTime[i][j] = INT_MAX / 2;
// }
// }
fill(pastTime[0], pastTime[(1<<(jvec.size()-1)) + 1]+20, INT_MAX / 2);
pastTime[0][0] = 0;
jobQueue.push(make_pair(0, 0));
valueQueue.push(0);
int maxValue = 0;
while (!jobQueue.empty()) {
pair<int, int> temp = jobQueue.front();
int value = valueQueue.front();
maxValue = max(value,maxValue);
jobQueue.pop();
valueQueue.pop();
for (int i = 1; i < jvec.size(); i++) {
Job tempJob = jvec[i];
if (!((1<<(i-1)) & temp.first)) { // not in pair
int start = max(tempJob.start, pastTime[temp.first][temp.second] + matDis[temp.second][i]);
if (start <= tempJob.end) {
pair<int, int> newPair((1<<(i-1)) + temp.first, i);
if (pastTime[newPair.first][i] > start + tempJob.time) {
pastTime[newPair.first][i] = start + tempJob.time;
if (!flag[newPair.first][i]) {
flag[newPair.first][i] = true;
jobQueue.push(newPair);
valueQueue.push(value + tempJob.value);
}
}
}
}
}
}
return maxValue;
}
int main(int argc, const char * argv[]) {
int M,Q;
scanf("%d %d %d",&N,&M,&Q);
while (M--)
{
int a,b,t;
scanf("%d %d %d",&a,&b,&t);
G[a].push_back(make_pair(b,t));
G[b].push_back(make_pair(a,t));
}
Job job0;
job0.loc = 1;
job0.value = 0;
job0.start = INT_MAX / 2;
job0.end = 0;
job0.time = INT_MAX / 2;
jvec.push_back(job0);
for (int i = 0; i < Q; i++) {
Job job;
scanf("%d %d %d %d %d",&job.loc,&job.start,&job.end,&job.time,&job.value);
jvec.push_back(job);
}
for(int i = 0;i <= Q; i++){
matDis[i][i]=0;
if(i==Q)break;
bool flag=false;
for(int j=0;j<i;j++){
if(jvec[i].loc==jvec[j].loc){
flag=true;
for(int k=0;k<=Q;k++){
matDis[i][k]=matDis[j][k];
}
break;
}
}
if(flag)continue;
dij(jvec[i].loc);
for(int j=i+1;j<=Q;j++){
matDis[i][j]=matDis[j][i]=dis[jvec[j].loc];
}
}
// int maxValue = 0;
// for (int i = 1; i < jvec.size(); i++) {
// bool flag[25];
// memset(flag, false, sizeof(flag));
// flag[i] = true;
//// cout<<maxPay(i,flag, 0, 0)<<endl;
// maxValue = max(maxValue,maxPay(i,flag, 0, 0));
// }
// cout<<maxValue<<endl;
cout<<loopMaxPay()<<endl;
return 0;
}
提交结果：
