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

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

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 64 Solved: 37
[Submit][Status][Discuss]

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

floyd+状压dp

n<=100所以直接先用floyd预处理要从i到j最多能吃到多胖

f[s][i]表示状态s下到第i个有宝藏的地方，是否能拿到所有s中的宝藏

当然最后还要考虑dis[id[i]][1]是否大于s状态下的宝藏数，取较小值就是答案了

#include<iostream>

#include<cstdio>

using namespace std;

int n,m,K,f[<<][],ans,dis[][],id[];

int main(){

    scanf("%d%d%d",&n,&m,&K);//M条双向通道,K个洞室，里面放有1捆干草

    for(int i=;i<=K;i++)scanf("%d",&id[i]);

    int x,y,z;

    for(int i=;i<=n;i++)dis[i][i]=0x3f3f3f3f;

    for(int i=;i<=m;i++){

        scanf("%d%d%d",&x,&y,&z);

        dis[x][y]=dis[y][x]=z;

    }

    for(int k=;k<=n;k++)

        for(int i=;i<=n;i++)

            for(int j=;j<=n;j++)

                if(i!=j&&i!=k&&j!=k){

                    if(dis[i][j]!=0x3f3f3f3f)dis[i][j]=max(dis[i][j],min(dis[i][k],dis[k][j]));

                    else dis[i][j]=min(dis[i][k],dis[k][j]);

                }

    int N=(<<K);

    for(int i=;i<=K;i++)f[(<<(i-))][i]=;

    for(int s=;s<N;s++){

        int num=;

        for(int i=;i<=K;i++)if(s&(<<(i-)))num++;

        for(int i=;i<=K;i++)

            if(s&(<<(i-)))

            for(int j=;j<=K;j++)

                if((!(s&(<<(j-))))&&num<=dis[id[i]][id[j]])f[s^(<<(j-))][j]|=f[s][i];

        for(int i=;i<=K;i++)

            if((s&(<<(i-)))&&f[s][i])

                ans=max(ans,min(dis[id[i]][],num));

    }

    printf("%d",ans);

}