题目描述

Description

很少人知道其实奶牛非常喜欢到洞穴里面去探险。
洞窟里有N(1≤N≤100)个洞室，由M(1≤M≤1000)条双向通道连接着它们．每对洞室间
至多只有一条双向通道．有K(1≤K≤14)个洞室，里面放有1捆干草．牛吃1捆干草，体重指数就会增加1．
贪吃的贝茜要到洞窟里面探险．她希望能吃尽量多的干草，但每条通道有一个宽度阈值，如果体重指数超过相应的阈值，贝茜就会被卡祝她从洞窟1出发，体重指数为0．在洞里溜达一圈后，她要返回洞窟1．
那她最多能吃多少捆干草呢？注意，贝茜经过一个洞室，不一定非要吃掉里面的干草．

Input

第1行输入N，M，K,之后K行每行一个整数，表示在这个洞室放有一捆干草；接下来M行每行三个整数，表示一条双向通道的起点终点和宽度阈值．

Output

最多能吃掉的干草数．

Sample Input

6 7 5
1
2
3
4
5
1 2 3
3 6 2
6 2 10
2 4 1
5 1 1
4 5 1
1 6 1

Sample Output

4

题目分析

f[s][i]表示 经过了状态s的关键点, 并且最后到达的是第i个关键点 的情况能不能达到

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m,k;
int vis[200];
int f[200][200];
int dp[1<<16][18];
void floyed()
{
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                f[i][j]=max(f[i][j],min(f[i][k],f[k][j]));
}
int num[1<<18],sa[200];
int main()
{   
    scanf("%d%d%d",&n,&m,&k);
    for(int x,i=1;i<=k;i++) 
        scanf("%d",&x),vis[x]=1,sa[++sa[0]]=x;
    for(int i=1;i<=n;i++) f[i][i]=n;
    for(int x,y,c,i=1;i<=m;i++)
        scanf("%d%d%d",&x,&y,&c),f[x][y]=f[y][x]=c;
    floyed();
    for(int i=1;i<(1<<k);i++) num[i]=num[i-(i&-i)]+1;
    for(int i=1;i<=k;i++) 
        if(f[1][sa[i]]) dp[0][i]=dp[1<<(i-1)][i]=1;
    for(int i=0;i<(1<<k);i++)
        for(int j=1;j<=k;j++)
            if(i&(1<<(j-1)))
                for(int z=1;z<=k;z++)
                {
                    if(z==j) continue;
                    if(i&(1<<(z-1))&&f[sa[j]][sa[z]]>=num[i^(1<<(z-1))])
                        dp[i][j]|=dp[i^(1<<(j-1))][z];
                }
    int ans=0;
    for(int i=0;i<(1<<k);i++)
        for(int j=1;j<=k;j++)
            if(dp[i][j]&&num[i]<=f[sa[j]][1])
                ans=max(ans,num[i]);
    printf("%d",ans);
    return 0;
}