BZOJ-3380: [Usaco2004 Open]Cave Cows 1 洞穴里的牛之一

[文章目录]

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;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注