P1547 Out of Hay 题解


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

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

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

评论

  • 马邦德
    tql
  • wfy2418978917
    66666
  • wfy2418978917
    稳中带皮
  • dread
    %%%
作者: Growl、 更新时间: 2019-08-27 17:14  在Ta的博客查看 举报    8  

最小生成树算法

根据题目描述,这道题是最小生成树

树是一种植物,木本植物之总名,主要由根、干、枝、叶、花、果组成

一个不存在回路的无向联通图叫做树

生成树:生成树是连通图的极小联通子图。(加边会出现回路,减边变为非连通图)

最小生成树: 生成树的各边权值总和最小的树(最小代价树)

最小生成树一般有两种算法:prim和kruskal。prim一般用于稠密图,kruskal用于稀疏图。

这里介绍一下kruskal。

kruskal算法的基本思想是:始终选择当前可用的最小权值边(贪心

因此很容易想到题目所求的最大边就是最后一条边(每次加边权取max也可以)。

那么怎么判断当前选择的边是否可用呢?

并查集

意思就是说,开始的每个点都是独立的集合,加边的时候就合并起来,如果已经是联通的就跳过。

附上代码```

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

using namespace std;

int fa[200004];
int n,m,l,r,tot,ans,k;

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}//快读 

struct node{
    int fir;//第一个点 
    int sec;//第二个点 
    int data;//边权 
}edge[400005];

inline int find(int x){
    if(x==fa[x])return x;
    else return fa[x]=find(fa[x]);
}

inline bool cmp(node a,node b){
    return a.data<b.data;//结构体排序 
}

inline void kruskal(){
    for(register int i=1;i<=m;i++){
        l=find(edge[i].fir);
        r=find(edge[i].sec);
        if(l==r)continue ;//如果联通就跳过 
        fa[l]=r;//否则就合并 
        k=edge[i].data;//每次更新边权,最后一条边为最大 
    //  maxn=max(maxn,edge[i].data);每次加边取max也可以 
        tot++;
        if(tot==n-1)break;
    }
}

int main(){
    n=read();
    m=read();
    for(register int i=1;i<=n;i++)
    fa[i]=i;//初始化并查集 
    for(register int i=1;i<=m;i++){
        edge[i].fir=read();
        edge[i].sec=read();
        edge[i].data=read();
    }

    sort(edge+1,edge+m+1,cmp);//将边权排序,每次加小的 
    kruskal();
    cout<<k;//我喜欢cout...

    return 0;
}

评论

  • stoorz
    666
  • 雄英天下第一
    ans = a[i].w 应该就可以了吧
  • 说好不哭
    最小生成树代码复制粘贴的题,居然黄色。。。弄得我刷的都没成就感了
  • Citus_Neru_index
    我用堆都骗了50分
作者: 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);//输出
}

评论

  • AFoeir
    写得真的很好
  • xiaopangfeiyu
    并茶集……
  • 余杭哲
    这函数,,,fa me?
作者: 卢本伟丶NiuB 更新时间: 2019-03-14 22:32  在Ta的博客查看 举报    5  

题目: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;
}

制作不易 不喜勿喷

评论

  • liyuting_233
    orz
作者: 0502wmyqaq 更新时间: 2019-06-15 22:48  在Ta的博客查看 举报    4  

最小生成树

更好的阅读体验

在这里介绍一下最小生成树的一个众所周知的算法—— 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道题

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



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