AcWing 1127. 香甜的黄油    原题链接    简单

作者： 作者的头像   1e9+7 ,  2020-04-08 12:44:20 ,  所有人可见 ,  阅读 3437

8


1

题目描述

农夫John发现了做出全威斯康辛州最甜的黄油的方法：糖。

把糖放在一片牧场上，他知道 N 只奶牛会过来舔它，这样就能做出能卖好价钱的超甜黄油。

当然，他将付出额外的费用在奶牛上。

农夫John很狡猾，就像以前的巴甫洛夫，他知道他可以训练这些奶牛，让它们在听到铃声时去一个特定的牧场。

他打算将糖放在那里然后下午发出铃声，以至他可以在晚上挤奶。

农夫John知道每只奶牛都在各自喜欢的牧场（一个牧场不一定只有一头牛）。

给出各头牛在的牧场和牧场间的路线，找出使所有牛到达的路程和最短的牧场（他将把糖放在那）。

数据保证至少存在一个牧场和所有牛所在的牧场连通。
输入格式

第一行: 三个数：奶牛数 N，牧场数 P，牧场间道路数 C。

第二行到第 N+1 行: 1 到 N 头奶牛所在的牧场号。

第 N+2 行到第 N+C+1 行：每行有三个数：相连的牧场A、B，两牧场间距 D，当然，连接是双向的。
输出格式

共一行，输出奶牛必须行走的最小的距离和。
数据范围

1≤N≤500
,
2≤P≤800,
1≤C≤1450,
1≤D≤255

样例

输入样例：

3 4 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5

输出样例：

8

题目分析

题意是这样的，P个顶点C条正权边，每个点有若干个奶牛
在1-n号点里面找一个点，使得所有点里面的奶牛到这个点的距离和最小

先看数据点800，边1500，每个点求一次
多源最短路，先想Floyd算一算会超
然后就是迪杰斯特拉（我不喜欢SPFA太玄学了）
算了一下问题不大 800x1500xlog1500大概1e7

时间复杂度O(PClogC)

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=3000,M=5000,C=1000;
int head[N],Next[M],ver[M],edge[M],d[N],v[N],total;
int n,m,c,x,y,z,num[C];
void add(int x,int y,int z)
{
    ver[++total]=y;
    edge[total]=z;
    Next[total]=head[x];
    head[x]=total;
}
int dijkstra(int s)
{
    memset(d,0x3f,sizeof(d));
    memset(v,0,sizeof(v));
    d[s]=0;
    priority_queue<pair<int ,int>>q;
    q.push({0,s});
    while(q.size())
    {
        x=q.top().second;
        q.pop();
        if(v[x])continue;
        v[x]=1;
        for(int i=head[x];i;i=Next[i])
        {
            y=ver[i],z=edge[i];
            if(d[y]>d[x]+z)
            {
                d[y]=d[x]+z;
                q.push({-d[y],y});
            }

        }
    }
    int res=0;
    for(int i=1;i<=n;i++)
        res+=num[i]*d[i];
    return res;
}
int main()
{
    cin>>c>>n>>m;
    while(c--)
    {
        cin>>x;
        num[x]++;
    }
    int ans=1<<29;
    while(m--)
    {
        cin>>x>>y>>z;
        add(x,y,z);
        add(y,x,z);
    }
    for(int i=1;i<=n;i++)
        ans=min(ans,dijkstra(i));
    cout<<ans<<endl;
}

13 评论

用户头像
Z_char   2020-12-27 20:05         踩      回复

我复制了您的代码
对于这一组数据

3 5 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5

应该输出$8$.(比较容易手推？
您的代码输出:-1111638595

用户头像
林苡涵   2021-09-11 21:40         踩      回复

少了 if(dist[j]==INF) return INF; 用来判断此时选取的牧场牛无法到达

用户头像
如梦凉生   2022-04-01 09:59    回复了 林苡涵 的评论         踩      回复

大佬你好，感觉给出的这几个边就把这四个点连通了呀，为什么会出现无法到达的情况呢

用户头像
I_can_do_wonders   2022-07-20 18:01    回复了 如梦凉生 的评论         踩      回复

仔细看数据，有5个点，而给出的几个边只涉及到了4个点，也就是说有一个点孤零零的

用户头像
如梦凉生   2022-07-21 21:07    回复了 I_can_do_wonders 的评论         踩      回复

好的谢谢大佬⊙▽⊙

用户头像
楚天   2020-09-19 19:03         踩      回复

大佬我问一个小问题，就是为什么我跑出来的是负数

memset(0x3f)就挂了，但是改成memset(0x7f)，就能a了，这个是为什么


#include<bits/stdc++.h>
using namespace std;
queue<int >q;
const int maxn=1e6;
bool vis[maxn];
long long d[maxn];
long long num[maxn];
const int inf=0x3f3f3f3f;
int n,m,p;
int ne[maxn],ver[maxn],head[maxn],cnt,e[maxn];
void add(int u,int v,int c)
{
    ne[cnt]=head[u];
    ver[cnt]=v;
    e[cnt]=c;
    head[u]=cnt;
    cnt++;
}

long long spfa(int u)
{   
    memset(d,0x7f,sizeof(d));
    memset(vis,0,sizeof(vis));
    q.push(u);
    d[u]=0;
    vis[u]=1;
    while(q.size())
    {
        int x=q.front();
        q.pop();
        vis[x]=0;
        for(int i=head[x];i!=-1;i=ne[i])
        {
            int y=ver[i];
            if(d[y]>d[x]+e[i])
            {
                d[y]=d[x]+e[i];
                if(vis[y]==0)
                {   
                    q.push(y);
                    vis[y]=1;
                }
            }
        }
    }
    long long res=0;
    // for(int i=1;i<=n;i++)
    // cout<<num[i]<<" "<<d[i]<<endl;
    for(int i=1;i<=n;i++)
        res=(res+num[i]*d[i]);
    return res;
}
int main()
{
    memset(head,-1,sizeof(head));
    scanf("%d%d%d",&p,&n,&m);
    for(int i=1;i<=p;i++)
    {
        int x;
        cin>>x;
        num[x]++;
    }
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
    }
    // for(int i=1;i<=n;i++)
    // spfa(i),puts(" ");
    long long ans=inf;
    for(int i=1;i<=n;i++)
    ans=min(ans,spfa(i));
    cout<<ans<<endl;
}
用户头像
1e9+7   2020-09-21 15:57         踩      回复

两个0x7f进行+运算的时候会溢出int类型的数据范围上限

用户头像
Z_char   2020-12-27 20:00         踩      回复

老哥…仔细读题啊，数据保证至少存在一个牧场和所有牛所在的牧场连通。，这个的意思是，不保证图联通，但是一定有解，也就是你的

for(int i=1;i<=n;i++)
        res=(res+num[i]*d[i]);

是有问题的。
因为我可能有一个没有牛的牧场，它不和其他牧场联通，我只需要保证存在那么一个牧场，能连接所有牛即可，完全可能存在这么一个没有牛的牧场，是不联通的，那么你这里$Dij$之后，没有到达的有牛的点，$dis$正无穷，$num$有牛，你乘起来不就爆$long long$了么？不就负数了么？那你取$min$不就错了嘛？
至于为什么$0x7f$会对，可能是数据比较水？恰好让$0x7f$可以变回正无穷吧？这样就不影响取$min$了。我觉得可以构造数据卡掉$0x7f$。
正确的写法应该这样

for(int i=1;i<=n;i++)
    {
        if(i!=s){
            if(d[i] && !vis[i])return INF;
            res+=d[i]*dis[i];
        }
    }

如果这个点对于某些有牛的点，它不能到达，就说明它没法作为答案，返回INF不影响取$min$

用户头像
楚天   2020-12-28 06:34    回复了 Z_char 的评论         踩      回复

谢谢大佬

用户头像
哈哈哈hh   2020-07-09 21:31         踩      回复

大佬，为什么push(-d[y],y)啊， 不应该是d[y],y 吗

用户头像
1e9+7   2020-07-13 16:04         踩      回复

因为priority_queue是大根堆，取出的都是最大值，取一个相反数作为优先权如果-d[y]最大那么保证了取出来得d[y]最小，功能类似于重载，这样写起来比较省事

用户头像
可持久化wql   2020-08-15 22:07    回复了 1e9+7 的评论         踩      回复

改成小根堆不香吗

用户头像
1e9+7   2020-09-21 15:57    回复了 可持久化wql 的评论         踩      回复

当然香，个人习惯不一样