[文章目录]
Description
洞窟里有N(1≤N≤100)个洞室，由M(1≤M≤1000)条双向通道连接着它们．每对洞室间至多只有一条双向通道．有K(1≤K≤14)个洞室，里面放有1捆干草．牛吃1捆干草，体重指数就会增加1．贪吃的贝茜要到洞窟里面探险．她希望能吃尽量多的干草，但每条通道有一个宽度阈值，如果体重指数超过相应的阈值，贝茜就会被卡祝她从洞窟1出发，体重指数为0．在洞里溜达一圈后，她要返回洞窟1． 那她最多能吃多少捆干草呢？注意，贝茜经过一个洞室，不一定非要吃掉里面的干草．
floyd+状压DP。
floyd求出两个点之间路径上边最小值的最大值。之后考虑每个点只会被吃一次，那么我们将吃过的状态和当前在哪个点设为状态dp[s][i]表示吃的状态为s，当前在i这个点最大的体重指数。时间复杂度O(n^3+2^k*k*k)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,num,a[20],mp[210][210];
int dp[1<<15][15];
int main()
{
scanf("%d%d%d",&n,&m,&num);
for(int i=1;i<=num;++i) scanf("%d",a+i);
int x,y,z;
memset(mp,-1,sizeof mp);
for(int i=1;i<=m;++i)
{
scanf("%d%d%d",&x,&y,&z);
mp[x][y]=mp[y][x]=z;
}
for(int i=1;i<=n;++i) mp[i][i]=20;
for(int k=1;k<=n;++k)
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
mp[i][j]=max(mp[i][j],min(mp[i][k],mp[k][j]));
for(int i=1;i<=num;++i)
if(mp[1][a[i]]>=0) dp[1<<(i-1)][i-1]=1;
for(int s=1;s<(1<<num);++s)
for(int i=0;i<num;++i) if(s|(1<<i))
for(int j=0;j<num;++j) if(!(s&(1<<j)))
dp[s|(1<<j)][j]=max(dp[s|(1<<j)][j],min(dp[s][i],mp[a[i+1]][a[j+1]])+1);
int ans=0;
for(int i=0;i<num;++i)
ans=max(ans,min(dp[(1<<num)-1][i],mp[a[i+1]][1]));
printf("%d",ans);
return 0;
}