题干：
Brickgao, who profited from your accurate calculating last year, made a great deal of money by moving bricks. Now he became ``gay shy fool'' again and recently he bought an iphone and was deeply addicted into a cellphone game called Ingress. Now he is faced with a problem so he turns to you for help again. We make some slight modifications based on the original rules, so please draw attention to the details below.
There are NN portals (indexed from 1 to NN) around Brickgao's home, and he can get some substances called XM by hacking the portals. It's known that for each portal ii, he can get AiAi XM during the first hack, and after each hack, the amount of XM he will get during the next hack will decrease by BiBi. If the amount of XM he can get is less than or equal to zero, Brickgao can't get XM from that portal anymore. For the ii-th portal, if Ai=10,Bi=2Ai=10,Bi=2 and he hacks 3 times, he will get 10, 8, 6 XM during each hack.
There are MM bidirectional roads between some pairs of portals and between Brickgao's home and some portals. Now he is eager to start his Ingress journey from home and finally return home, but due to the extremely hot weather, Brickgao will feel sick when you hack more than KK times or the distance he covers is more than LL. So how much XM he can get at most during this journey?
Input
The first line contains a single integer T(T≤20)T(T≤20), indicating the number of test cases.
The first line of each case are four integers N(1≤N≤16),M(0≤M≤N(N+1)2),K(1≤K≤50)N(1≤N≤16),M(0≤M≤N(N+1)2),K(1≤K≤50) and L(2≤L≤2000)L(2≤L≤2000).
The second line of each case contains NN non-negative integers where the ii-th denotes Ai(Ai≤500)Ai(Ai≤500).
The third line of each case contains NN non-negative integers where the ii-th denotes Bi(Bi≤50)Bi(Bi≤50).
Each of next MM line contains 3 non-negative integers u,v(0≤u,v≤n)u,v(0≤u,v≤n) and c(0≤c≤1000)c(0≤c≤1000) , denotes that there is a road with the length of cc between the uu-th and the vv-th portal. If uu or vv equals to 0, it means Brickgao's home.
Output
For each test case, output the case number first, then the amount of maximum XM Brickgao can get.
Sample Input
2
1 1 3 2
5
3
0 1 1
3 6 3 5
10 7 5
2 3 1
0 1 3
0 2 1
0 3 1
1 2 2
2 3 3
1 3 4 Sample Output
Case 1: 7
Case 2: 16 题目大意：
n（<=16）个点（其实还有个0点为home），m（<=n^2）条双向边和边权（代表两点之间距离<=1000），K（<=50）次hack机会，最远走L（<=2000）路程
每个点的初始点权为a[i](<=500)，每个点每hack一次点权下降b[i](<=50)（变为负则当然就不选啦）
对于每个点，可以只经过不hack，也可以到这个点之后一次性hack多次。
一个人从home出发，最多hackK次，问在路程不超过L的情况下，可以获得的最大价值。
解题报告：
因为可以只经过不hack，所以先floyd跑一边最短路（套路了），然后不难发现可以认为：走过一个点之后不会再走回来，或者说，选择了这个点hack了，就不会回来再hack这个点（因为还要多走距离，何必呢）（emmm其实上面说走过一个点之后不会再走回来不太合适，因为毕竟因为最短路，所以可能还是要回来的（因为这一点是最短路需要经过的点嘛））这样我们只需要记录状态：走过了哪些点，当前在哪个点上，就可以跑(2^n * n)的dp了。
dp[sta][i]表示目前经过点的状态集合为i，当前所在点的位置为 i 的最小路径（当然要加上返程到0点的路径）
这是典型的旅行商问题。
由此得出所有可以到达的合法点集，其状态用2进制表示为sta。
对于每一个状态sta，只要dp[sta][i]有一个i符合<=L，那么称sta是合法状态。
然后依次枚举所有的合法sta，
对于每一个合法sta的所有点权，用贪心原则，用优先队列选取最大的权值。
AC代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 22;
int dis[MAX][MAX],dp[1<<17][17];
int a[MAX],b[MAX];
int n,m,k,L;
int up;
bool ok[1<<17];
void floyd() {
for(int k = 0; k<=n; k++) {
for(int i = 0; i<=n; i++) {
for(int j = 0; j<=n; j++) {
dis[i][j] = min(dis[i][j],dis[i][k] + dis[k][j]);
}
}
}
}
int tsp() {
int ans = 0;
for(int sta = 0; sta < up; sta++) ok[sta] = 0;
memset(dp,0x3f,sizeof dp);
dp[1][0]=0;
for(int sta = 0; sta < up; sta++) {
for(int i = 0; i<=n; i++) {
if(dp[sta][i] <= L) {
if(dp[sta][i] + dis[i][0] <= L) ok[sta] = 1;
for(int j = 1; j<=n; j++) {
dp[sta|(1<<j)][j] = min(dp[sta|1<<j][j], dp[sta][i] + dis[i][j]);
}
}
}
if(ok[sta]) {
priority_queue<PII> pq;
for(int i = 1; i<=n; i++) {
if((sta&(1<<i) )!= 0) pq.push(pm(a[i],b[i]));
}
int tmp = 0;
for(int i = 1; i<=k; i++) {
if(pq.empty()) break;
PII cur = pq.top();pq.pop();
tmp += cur.F;
cur.F -= cur.S;
if(cur.F > 0) pq.push(pm(cur.F,cur.S));
}
ans = max(ans,tmp);
}
}
return ans;
}
int main()
{
int t,iCase=0;
cin>>t;
while(t--) {
scanf("%d%d%d%d",&n,&m,&k,&L);
up = (1<<(n+1));
memset(dis,0x3f,sizeof dis);
for(int i = 0; i<=n; i++) dis[i][i]=0;
for(int i = 1; i<=n; i++) scanf("%d",a+i);
for(int i = 1; i<=n; i++) scanf("%d",b+i);
for(int q,w,e,i = 1; i<=m; i++) {
scanf("%d%d%d",&q,&w,&e);
if(e < dis[q][w]) dis[q][w]=dis[w][q]=e;
}
floyd();
printf("Case %d: %d\n",++iCase,tsp());
}
return 0 ;
} 贴另一个做法：https://blog.csdn.net/qq_37025443/article/details/83513413
京公网安备 11010502036488号