首页 > 代码库 > Bzoj 3380: [Usaco2004 Open]Cave Cows 1 洞穴里的牛之一
Bzoj 3380: [Usaco2004 Open]Cave Cows 1 洞穴里的牛之一
3380: [Usaco2004 Open]Cave Cows 1 洞穴里的牛之一
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 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
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
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[1<<14][15],ans,dis[110][110],id[15];int main(){ scanf("%d%d%d",&n,&m,&K);//M条双向通道,K个洞室，里面放有1捆干草 for(int i=1;i<=K;i++)scanf("%d",&id[i]); int x,y,z; for(int i=1;i<=n;i++)dis[i][i]=0x3f3f3f3f; for(int i=1;i<=m;i++){ scanf("%d%d%d",&x,&y,&z); dis[x][y]=dis[y][x]=z; } for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;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=(1<<K); for(int i=1;i<=K;i++)f[(1<<(i-1))][i]=1; for(int s=1;s<N;s++){ int num=0; for(int i=1;i<=K;i++)if(s&(1<<(i-1)))num++; for(int i=1;i<=K;i++) if(s&(1<<(i-1))) for(int j=1;j<=K;j++) if((!(s&(1<<(j-1))))&&num<=dis[id[i]][id[j]])f[s^(1<<(j-1))][j]|=f[s][i]; for(int i=1;i<=K;i++) if((s&(1<<(i-1)))&&f[s][i]) ans=max(ans,min(dis[id[i]][1],num)); } printf("%d",ans);}
Bzoj 3380: [Usaco2004 Open]Cave Cows 1 洞穴里的牛之一
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。