P1547 Out of Hay 题解


以下题解仅供学习参考使用。

抄袭、复制题解,以达到刷AC率/AC数量或其他目的的行为,在洛谷是严格禁止的。

洛谷非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看洛谷社区规则

评论

  • stoorz
    666
  • 雄英天下第一
    ans = a[i].w 应该就可以了吧
  • 杰伦小迷弟
    最小生成树代码复制粘贴的题,居然黄色。。。弄得我刷的都没成就感了
作者: SSL_XXY_BlackCloud 更新时间: 2018-02-04 08:59  在Ta的博客查看 举报    7  

一开始看到最小生成树,果断prim然后。。。果断WA了5个点,所以就重新审视了一下题目,发现其实只要排个序(最长边嘛),连个边(生成树嘛),就可以了。

先发个50分的。。。

```C++
#include<bits/stdc++.h>
#define INF 2147483648
#define r(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int l[2001][2001],n,m,x,y,z,dis[2001],minn,k,ans;//只弄了2000乘2000.。。
bool vis[2001];
int main()
{
    r(i,0,2000) r(j,0,2000) l[i][j]=INF/4;
    scanf("%d %d",&n,&m);
    r(i,1,m)
     {
        scanf("%d %d %d",&x,&y,&z);if(x==y) continue;//自环判断
        l[x][y]=l[y][x]=min(l[x][y],min(z,l[y][x]));//重边判断
     }
    r(i,1,n)
     dis[i]=l[1][i];dis[1]=0;//初始化
    r(i,1,n-1)
    {
        minn=INF/4;k=0;vis[i]=true;
        r(j,1,n)
         if(dis[j]<minn&&!vis[j])//找最短的
          {
            minn=dis[j];//赋值
            k=j;//标记
          }
        vis[k]=true;//标记
        if(!k) break;//找不到直接结束
        if(minn<=INF/4) ans=max(ans,minn);//找到了才赋值
        r(j,1,n)
         if(l[j][k]<dis[j])//修整
          dis[j]=l[j][k];
    }
    printf("%d",ans);//输出
}

代码AC

```C++
#include<bits/stdc++.h>
#define r(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int f[2001],n,m,x,y,z,tat,ans;//tat是当前连边个数,f是并查集数组,ans是最终答案
struct node{int from,to,w;}a[20001];//结构体,等下直接排序
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}//找祖宗
void judge(int x,int y){f[find(x)]=find(y);}//连边
bool too(int x,int y){return find(x)==find(y);}//判断两个元素是否在同一集合内
bool cmp(node x,node y){return x.w<y.w;}//按按权值从小到大排(最小生成树)
int main()
{
    scanf("%d%d",&n,&m);r(i,1,n) f[i]=i;//初始化
    r(i,1,m)
     scanf("%d %d %d",&a[i].from,&a[i].to,&a[i].w);//输入
    sort(a+1,a+1+m,cmp);//排序
    r(i,1,m)
      if(!too(a[i].from,a[i].to))//没有连边
      {
        tat++;if(tat==n-1) {ans=max(ans,a[i].w);break;}//连,如果连到n-1条边就退出,最小生成树只需要n-1条边
        judge(a[i].from,a[i].to);//合并
        ans=max(ans,a[i].w);//统计最大值
      }
    printf("%d",ans);//输出
}

评论

  • 一念
    写得真的很好
  • xiaopangfeiyu
    并茶集……
作者: 優柔丨寡斷 更新时间: 2019-03-14 22:32  在Ta的博客查看 举报    4  

题目:out of hay(翻译:奶牛爱干草)

(花里胡哨的 没有用)

题目传送门 本人身为蒟蒻 来水一篇题解

题目还是好水的,最重要的是,题目把最主要的算法直接说出来了(真是直接啊)

------------------------------------------------------------分割线---------------------------------------------------------

最小生成树:

就是任意一棵最小生成树一定包含无向图中权值最小的边。

这里有Kruskal和Prim两种算法 个人推荐克鲁斯卡尔(稀疏图)

算法流程如下:
1.建立一个并查集,每个点各自构成一个集合。
2.把所有边按照权值从小到大排序,依次扫描每条边
3.若x,y连通,就忽略这条边,扫描下一条
4.否则,合并x,y所在的集合,并把z累加到答案里

时间复杂度为O(m log m)

下面上代码(想说的在里头)

#include<iostream>
#include<algorithm> 
using namespace std;
int n,m;
long long fa[100000001];
struct hay
{
    int x,y,z;
}a[10001];
inline bool cmp(hay a,hay b)
{
    return a.z<b.z;
}
//将权值从小到大排序 
inline int find(int t)
{
    if(fa[t]==t) return t;
    else return fa[t]=find(fa[t]);
} 
//路径压缩的日常。。。。 
inline void me(int r1,int r2)
{
    int s1=find(r1);
    int s2=find(r2);
    fa[s1]=s2;  
}
// 核心代码如下
inline void Kruskal()
{
    int k=0;
    int k1,k2;
    int ans=0;
    for(int i=1;i<=m;i++)
    {
        k1=find(a[i].x);
        k2=find(a[i].y);
        if(k1==k2) continue;//如果在一个集合内就忽略这条边,扫描下一条 
        k++;
        me(k1,k2);
        //合并 x y所在的集合 就是把边(x,y)放入最小生成树中 
        ans=max(a[i].z,ans);
        if(k==n-1) break;
        //到n-1条边停止,最小生成树只需要n-1条边 
    }
    cout<<ans;
}
int main()
{
    cin>>n>>m;
    int i;
    for(i=1;i<=n;i++)
    {
        fa[i]=i;
    }
    //并茶集初始化 
    //所有元素各自构成一个独立的集合 即为n棵点数为1的树 
    for(i=1;i<=m;i++)
    {
        cin>>a[i].x>>a[i].y>>a[i].z;
    } 
    sort(a+1,a+m+1,cmp);
    Kruskal();
    return 0;
}

制作不易 不喜勿喷

评论

  • 李玉庭
    orz
作者: 0502魏猛宇 更新时间: 2019-06-15 22:48  在Ta的博客查看 举报    2  

最小生成树

更好的阅读体验

在这里介绍一下最小生成树的一个众所周知的算法—— Kruskal(克鲁斯卡尔) 算法

前置技能:并查集

如果你不会请移步模板:P3367 【模板】并查集

这里举如下图的例子

这个图中一共有3个连通块,其中1、2为一个,4、5、6为一个,3为一个。

Kruskal

一般有下面几步:

1、将所有的边按边权从小到大排序(sort) ;

2、按从小到大排的顺序枚举所有的边 ;

3、如果是两个不同的集合,那么就计入最小生成树,合并集合。

算法流程:

1、初始化并查集 (你就是你爸爸)

    for(int i=1;i<=n;i++)
        fa[i]=i;

2、计数器(记录树边权和(ans),记录边数(bian))

    ans=0;
    bian=0;

3、排序所有的边权(这里用结构体来储存出发点,到达点,边权)

    struct chengshi
    {
        int x,y,v;
    }a[200001];
    sort(a+1,a+m+1,cmp);

4、枚举

    for(int i=1;i<=m;i++)
    {
        if(fa(a[i].x)!=fa(a[i].y))
        {
            lian(a[i].x,a[i].y);
            ans+=a[i].v;
            bian++;
            maxn=max(maxn,a[i].v);
        }
    }

5、这个题独特的一点,上面你也可能看出来了,它求的是最小生成树是最长边权,所以 (貌似记录器都没什么用)

            maxn=max(maxn,a[i].v);

上代码

并查集的部分不在解释,关于Kruskal的解释上面以有。

状态:AC

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

int n,m,fat[5001],x,y,v,shu,ans,bian,maxn=-1;
struct chengshi
{
    int x,y,v;
}a[200001];

int fa(int x)
{
    if(fat[x]!=x) fat[x]=fa(fat[x]);
    return fat[x];
}

void lian(int x,int y)
{
    int aa=fa(x),bb=fa(y);
    if(aa!=bb) fat[aa]=bb;
}

int cmp(chengshi a,chengshi b) //快排的cmp函数
{
    if(a.v<b.v) return 1;
    else return 0;
}

int max(int a,int b) {return a>b?a:b;}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y>>v;
        a[i].x=x;
        a[i].y=y;
        a[i].v=v;
    }
    for(int i=1;i<=n;i++) fat[i]=i;
    sort(a+1,a+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        if(fa(a[i].x)!=fa(a[i].y))
        {
            lian(a[i].x,a[i].y);
            ans+=a[i].v;
            bian++;
            maxn=max(maxn,a[i].v);
        }
    }
    cout<<maxn;
    putchar('\n'); //换行,比较快吧
    return 0;
}

/*
3 3
1 2 23
2 3 1000
1 3 43

*/

评论

  • 火之意志
    还没有评论
  • 离火喵
    写下你的评论...
作者: liuyifan 更新时间: 2018-08-25 18:19  在Ta的博客查看 举报    1  

这道题就是个最小生成树的模板题

本蒟蒻表示:优先队列是什么?不知道

所以就老老实实的用Kruskal+并查集模板做吧,时间复杂度O(nlogn+np(n)),p(n)是一次并查集操作的复杂度)

对于像我一样啥都不懂的蒟蒻可以参考此链接:Kruskal(内容仅供参考,与我无关)

code:(所有模板均为手写,不含其实是不会STL)

#include<bits/stdc++.h>
#define reg register
using namespace std;
int n,m,p,s=0,cnt=0f[100005];
struct node{int a,b,x;}a[100005];//从A到B有一条边长为X的有向边
bool cmp(const node &ne,const node &be){return ne.x<be.x;}//将node按照边长X排序,如果要改成从大到小就把<换成>
inline int getfather(int x)
{
    if(f[x]==x) return x;
    f[x]=getfather(f[x]);
    return f[x],
}//并查集路径压缩,应该都会吧
原理:getfather(a)把a点到根节点的之间的所有节点(包括a)都接到了根节点的下方,显著降低了每次查询的复杂度
inline void kruskal()//Krustal模板,原理如上
{
    reg int cnt=0,x,y;
    for(int i=1;i<=n;i++)f[i]=i;
    for(int i=1;i<=m;i++)
    {
        x=getfather(a[i].a);//压缩路径
        y=getfather(a[i].b);//同上
        if(x==y)continue;
        s=max(a[i].x,s);//最长边的长度
        f[x]=y;
        cnt++.
        if(cnt==n-1)break;
    }
    if(cnt<n-1)printff("-1");//操作不到n-1次(边不到n-1条),不存在最小生成树
    else printf("%d",s);//输出解
}
int main()
{
    scanf("%d%d",&n,&m);//scanf不用讲了吧
    for(reg int i=1;i<=m;i++)scanf("%d%d%d",&a[i].a,&a[i].b,&a[i].x);
    sort(a+1,a+m+1,cmp);//结构体和多维数组的快排必须手写cmp(比较)函数
    kruskal();
    return 0
}

拒绝抄袭,共建和谐洛谷

提示:本题的代码可以和P1111通用,可以一次水2道题

评论

  • Destroy_create
    还没有评论
  • wyhwyh
    还没有评论
  • 神兵qqq1112
    还没有评论
  • 离火喵
    还没有评论
作者: tm_337045319 更新时间: 2018-08-07 17:00  在Ta的博客查看 举报    2  

这道题就是最小生成树的入门题。

解决它的一般用两种算法:

Kruskal算法和Prim算法

首先讲一下Kruskal算法。

1.将所有边从小到大排序。

2.从小到大取边,且两点不在同一连通分量上(取n-1条边)

#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
int f[2001];//f[i]表示i节点的父结点
long long maxn;
struct Edge//结构体 
{
    int u;
    int v;
    long long w;
}edge[10001];
bool cmp(Edge x,Edge y)//比较 
{
    return x.w<y.w; 
}
int find(int x)//并查集函数,用来查找该节点的最老的祖先 
{
    if(f[x]==x)
    {
        return x;
    }
    return f[x]=find(f[x]);//路径压缩 
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        f[i]=i;//初始化,把所有节点的父节点都当做自己 
    }
    for(int i=1;i<=m;i++)
    {
        cin>>edge[i].u>>edge[i].v>>edge[i].w;
    }
    sort(edge+1,edge+m+1,cmp);//STL sort
    int cnt=0;
    for(int i=1;i<=m;i++)
    {
        int fx=find(edge[i].u);
        int fy=find(edge[i].v);
        if(fx!=fy)//如果两点不在一连通分量上 (两点的最老祖先不同) 
        {
            f[fx]=fy;//合并 
            maxn=max(maxn,edge[i].w);//更新最大值 
            cnt++;
        }
        if(cnt==n-1)//选够n-1条边 
        {
            break;
        }
    }
    cout<<maxn;
}

而Prim算法则是用到另一种思想(废话)

1.分为两个集合,第一个集合表示已挑选的点,另一个表示未挑选的点。

2.将随便一点放入已挑选的点的集合内。

3.每次找一条最短的边,此边两点必须在两个不同集合中。

4.将另一点放入已挑选的点集合内,并删除原有位置。

5.重复步骤3,直到未挑选的点的集合为空,算法结束。

至于代码请参考各位大佬的。

比较

时间复杂度: Kruskal O(eloge),适合稀疏图。

Prim O(n^2),适合稠密图。

就个人而言,更喜欢K氏算法。

 
反馈
如果你认为某个题解有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。