剪切板()-其他

发表于： 3月 17, 2023 3月 17, 2023
分类：其他
标签：其他

剪切板()

最小生成树

kruskal

模板题（AcWing.859）

一种最小生成树算法，时间复杂度 \(\operatorname{O(mlogm)}\) ，主要用于稀疏图。

思路

直接对边进行排序，用并查集维护边的集合，如果两条边不在同一集合则合并两个集合，并累计答案。

如果保留的边数小于点数-1 ，说明不存在最小生成树。

代码

#include <bits/stdc++.h>
#define ll long long
#define rll register ll
#define cll const ll
#define N 1000005
using namespace std;
inline ll read()
{
    rll x=0;bool f=1;register char c=getchar();
    while(c<48||c>57){if(c=='-') f=0;c=getchar();}
    while(c>=48&&c<=57){x=x*10+(c^48);c=getchar();}
    return f?x:-x;
}
inline void write(ll x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+48);
}
struct node{ll x,y,z;}e[N];
inline bool cmp(node a,node b){return a.z<b.z;}
cll n=read(),m=read();
ll ans,cnt,f[N];
inline ll find(ll x)
{
    if(x==f[x]) return x;
    return f[x]=find(f[x]);
}
int main()
{
    for(rll i=1;i<=m;i++)
        e[i].x=read(),e[i].y=read(),e[i].z=read();
    sort(e+1,e+1+m,cmp);
    for(rll i=1;i<=n;i++) f[i]=i;
    for(rll i=1;i<=m;i++)
    {
        cll x=find(e[i].x),y=find(e[i].y);
        if(x==y) continue;
        f[x]=y,ans+=e[i].z,cnt++;
    }
    if(cnt<n-1) cout << "impossible";
    else write(ans);
    return 0;
}

prim

一种最小生成树算法，时间复杂度 \(\operatorname{O(n^2)}\) ，主要用于稠密图。

思路

为了在稠密图上比 kruskal 更胜一筹， prim 利用最短路的思想巧妙地避开了边数对时间复杂度的影响。

用 \(dis\) 数组维护每个点到集合的距离，每次更新寻找离集合最近的点并将它加入最小生成树。

判断无解：如果全局最小值是孤立点，那么最小生成树不存在。

代码

#include <bits/stdc++.h>
#define ll long long
#define rll register ll
#define cll const ll
#define N 505
using namespace std;
inline ll read()
{
    rll x=0;bool f=1;register char c=getchar();
    while(c<48||c>57){if(c=='-') f=0;c=getchar();}
    while(c>=48&&c<=57){x=x*10+(c^48);c=getchar();}
    return f?x:-x;
}
inline void write(ll x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+48);
}
cll n=read();
ll m=read(),ans,dis[N],g[N][N];
bool flag[N];
inline void prim()
{
    memset(dis,0x3f,sizeof dis);
    dis[1]=0;
    for(rll i=0;i<n;i++)
    {
        rll t=-1;
        for(rll j=1;j<=n;j++)
            if(!flag[j]&&(t==-1||dis[t]>dis[j])) t=j;
        if(i&&dis[t]>=0x3f3f3f3f3f3f3f3f){cout << "impossible";return;}
        if(i) ans+=dis[t];
        for(rll j=1;j<=n;j++)
            dis[j]=min(dis[j],g[t][j]);
        flag[t]=1;
    }
    write(ans);
}
int main()
{
    memset(g,0x3f,sizeof g);
    while(m--)
    {
        cll a=read(),b=read(),c=read();
        g[a][b]=g[b][a]=min(g[a][b],c);
    }
    prim();
    return 0;
}

————————