题解 P5096 【[USACO2004OPEN]Cave Cows 1 洞穴里的牛之一】

_蒟蒻__ · 2019-07-02 10:07:03 · 题解

看到不少大佬都用状压DP过的，

但是，

凭良心估计一下自己的实力，发现本蒟蒻并不会啊……

重新思考一下，设dis[i][j]表示从i到j的最短边（限制收集）的长度。N<=100,可以用floyd处理。

最后贪心一下，把有干草的点i按照dis[1][i]排序，从最小的开始选。

蒟蒻水平低，还望各位大佬斧正。

#include<cstdio>
#include<algorithm>
#define res register int
using namespace std;

const int inf=23333333;
int n,m,k;
int dis[110][110];
int a[110],b[110];

template<class T>
inline void read(T& v)
{
    char c=getchar();v=0;
    while(c<'0'||c>'9'){c=getchar();}
    while(c>='0'&&c<='9'){v=(v<<3)+(v<<1)+(c^'0');c=getchar();}
}

inline void floyd()
{   
    for(res i=1;i<=n;i++)dis[i][i]=inf;

    for(res t=1;t<=n;t++)
     for(res i=1;i<=n;i++)
      for(res j=1;j<=n;j++)
      {
          dis[i][j]=dis[j][i]=max(dis[i][j],min(dis[i][t],dis[t][j]));
            //考虑是否要从t点绕行（因为是无向图，且无次数限制，可以随便走） 
      }
}

inline int solve()
{
    for(res i=1;i<=k;i++)b[i]=dis[1][a[i]];

    sort(b+1,b+k+1);

    int ans=0;

    for(res i=1;i<=k;i++)//贪心在这里 
    if(b[i]>ans)//当前已经拥有ans个，判断是否能够从这走。 
    {
        ans++;
    }

    return ans;
}

int main()
{   
    read(n),read(m),read(k);

    for(res i=1;i<=k;i++)
        read(a[i]);

    int x,y,w;
    for(res i=1;i<=m;i++)
    {
        read(x),read(y),read(w);
        dis[x][y]=dis[y][x]=max(dis[x][y],w);
    }

    floyd();

    printf("%d",solve());

    return 0;
}