P1340 兽径管理题解 » 老官童鞋gogo的博客

题目传送门

题解

题目理解与强调

这道题目是的本质是最小生成树，题意为共有$ n $个点$ m $ 条边，最初这$ n $个点之间没有边，每次只加入$ 1 $条边，问用$ n-1 $条边将所有点连接起来的最短长度是多少，如果当前的边不足以连接所有的点，就输出$ -1 $。

思路分析（暴力）

这道题的算法使用Kruskal算法求解

首先是处理读入的边，每条边记录它是有哪个点指向哪个点，记录这条边的权值和加入的时间，对它的权值进行排序。

然后处理答案的最小值，枚举时间，每加入一条边进行一次Kruskal算法，在Kruskal内部，我们从最小的边开始枚举，如果当前的边加入的时间大于我们最开始枚举的时间就跳过，寻找下一条边，然后计算输出答案如果并查集中相连接的点小于$ n $，则说明不是所有的点都联通了，那么输出$ -1 $。

这种方法暴力，但是能过，但也只是卡着时间过，代码中加入了大量的register

代码（暴力）

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define ll long long
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define fi first
#define se second
#define pr(x) cerr<<#x<<"="<<(x)<<endl
#define pri(x,lo) {cerr<<#x<<"={";for (int ol=0;ol<=lo;ol++)cerr<<x[ol]<<",";cerr<<"}"<<endl;}
#define inf 100000000
#define N 1000
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-48;ch=getchar();}
    return x*f;
}
struct Node
{
    int to,fr,num,w;
}e[100001];
int g[100001],nxt,fa[201],n,w;
inline void add(register int u,register int v,register int w,register int num)
{
    e[++nxt].to=v;
    e[nxt].fr=u;
    e[nxt].w=w;
    e[nxt].num=num;
}
bool cmp(Node a,Node b)
{
    return a.w<b.w;
}
inline int find(register int x)
{
    return fa[x]==x?x:find(fa[x]);
}
inline void kruskal(register int x)
{
    for(register int i=1;i<=n;i++)
    {
        fa[i]=i;
    }
    register int ans=0,sum=0;
    for(register int i=1;i<=nxt;i++)
    {
        if(e[i].num>x)   continue;
        register int fx=find(e[i].fr);
        register int fy=find(e[i].to);
        if(fx!=fy)
        {
            fa[fx]=fy;
            ans+=e[i].w;
            sum++;
        }
        if(sum==n-1)
        {
            printf("%d\n",ans);
            return;
        }
    }
    printf("-1\n");
}
int main()
{
    n=read(),w=read();
    for(register int i=1;i<=w;i++)
    {
        register int u=read(),v=read(),c=read();
        add(u,v,c,i);
    }
    sort(e+1,e+nxt+1,cmp);
    for(register int i=1;i<=w;i++)
    {
        kruskal(i);
    }
    return 0;
}