05:Cave Cows 1 洞穴里的牛之一
2018-06-17 22:11:47来源:未知 阅读 ()
- 总时间限制:
- 10000ms
- 单个测试点时间限制:
- 1000ms
- 内存限制:
- 262144kB
- 描述
-
很少人知道其实奶牛非常喜欢到洞穴里面去探险。洞窟里有N(1≤N≤100)个洞室,由M(1≤M≤1000)条双向通道连接着它们.每对洞室间至多只有一条双向通道.有K(1≤K≤14)个洞室,里面放有1捆干草.牛吃1捆干草,体重指数就会增加1.贪吃的贝茜要到洞窟里面探险.她希望能吃尽量多的干草,但每条通道有一个宽度阈值,如果体重指数超过相应的阈值,贝茜就会被卡祝她从洞窟1出发,体重指数为0.在洞里溜达一圈后,她要返回洞窟1. 那她最多能吃多少捆干草呢?注意,贝茜经过一个洞室,不一定非要吃掉里面的干草.
- 输入
- 第1行输入N,M,K,之后K行每行一个整数,表示在这个洞室放有一捆干草;接下来M行每行三个整数,表示一条双向通道的起点终点和宽度阈值.
- 输出
- 最多能吃掉的干草数.
- 样例输入
-
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
- 样例输出
-
4
- 来源
- USACO 2004 Open Orange
- 思路:贪心,把每个稻草的阈值都排一个序,能吃的就吃
- 注意几个细节:
- 1、要特判一号洞穴有艹的情况
- 2.、最后要写>
-
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 using namespace std; 7 const int MAXN=4001; 8 const int maxn=0x3f; 9 void read(int &n) 10 { 11 char c='+';int x=0;bool flag=0; 12 while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;} 13 while(c>='0'&&c<='9') 14 x=(x<<1)+(x<<3)+c-48,c=getchar(); 15 flag==1?n=-x:n=x; 16 } 17 int n,m,k; 18 struct node 19 { 20 int have; 21 int need; 22 int pos; 23 }a[MAXN]; 24 int map[MAXN][MAXN]; 25 int dis[MAXN][MAXN]; 26 int comp(const node &a,const node &b) 27 { 28 if(a.have==b.have) 29 return a.need<b.need; 30 else 31 return a.have>b.have; 32 } 33 int main() 34 { 35 read(n);read(m);read(k); 36 int num=k; 37 for(int i=1;i<=k;i++) 38 { 39 int p; 40 read(p); 41 a[p].have=1; 42 a[i].pos=i; 43 } 44 memset(map,maxn,sizeof(map)); 45 for(int i=1;i<=m;i++) 46 { 47 int x,y,z; 48 read(x);read(y);read(z); 49 map[x][y]=z; 50 map[y][x]=z; 51 } 52 53 for(int i=1;i<=n;i++) 54 map[i][i]=0; 55 56 for(int k=1;k<=n;k++) 57 for(int i=1;i<=n;i++) 58 for(int j=1;j<=n;j++) 59 if(map[i][j]<maxn) 60 map[i][j]=max(map[i][j],min(map[i][k],map[k][j])); 61 else 62 map[i][j]=min(map[i][k],map[k][j]); 63 64 for(int i=1;i<=n;i++) 65 if(a[i].have) 66 a[i].need=map[1][i]; 67 68 69 sort(a+1,a+n+1,comp); 70 71 int now=0; 72 int flag=0; 73 for(int i=1;i<=num;i++) 74 { 75 // if(a[i].have==0)break; 76 if(a[i].have&&a[i].pos==1) 77 { 78 flag=1; 79 continue; 80 } 81 if(a[i].need>now) 82 now++; 83 84 } 85 if(flag==1) 86 now++; 87 printf("%d",now); 88 return 0; 89 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- lost cows 2020-02-12
- P2858 [USACO06FEB]奶牛零食Treats for the Cows 2018-06-17
- P2915 [USACO08NOV]奶牛混合起来Mixed Up Cows 2018-06-17
- P2742 [USACO5.1]圈奶牛Fencing the Cows 2018-06-17
- 洛谷P2147 [SDOI2008]Cave 洞穴勘测 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash