总时间限制: 

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 5123451 2 33 6 26 2 102 4 15 1 14 5 11 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 node19 {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     else31         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 } 

 

05:Cave Cows 1 洞穴里的牛之一