题解：UVA11631 Dark roads

· · 题解

题目传送门

博客食用效果更佳！！！

一句话题意

请你根据所出数据求出最小生成树的大小，得出边权之和与这棵最小生成树大小的差。

最小生成树

最小生成树（Minimum Spanning Tree，简称 MST）是一种在连通图中生成一棵树的算法，该树包含了图中所有的顶点，并且边的权值之和最小。

最常用的两种最小生成树算法是 Prim 算法和 Kruskal 算法。

Prim 算法：
    1. 选择一个起始顶点，将其加入最小生成树中。
    2. 从与最小生成树相邻的顶点中选择一个权值最小的边，将其加入最小生成树。
    3. 重复上述步骤，直到最小生成树包含了图中所有的顶点。 
Kruskal 算法：
    1. 将图中的所有边按照权值从小到大进行排序。
    2. 依次选择权值最小的边，如果该边的两个顶点不在同一个连通分量中，则将其加入最小生成树，并将这两个顶点合并到同一个连通分量中。
    3. 重复上述步骤，直到最小生成树包含了图中所有的顶点。

但是这里的数据范围明显开不下一个 cost 二维数组，所以本题用 Prim 做法会更加复杂（使用邻接表存储变量，没试过），故考虑 Kruskal。

MLE代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+2;
int n,m,cost[N][N],mincost[N],sum;
bool vis[N];
int prim()//最小生成树
{
    for(int i=0;i<n;i++)
    {
        mincost[i]=INT_MAX;
        vis[i]=false;
    }
    mincost[1]=0;
    int res=0;
    while(true)
    {
        int v=-1;
        for(int u=0;u<n;u++)
        {
            if(!vis[u]&&(v==-1||mincost[u]<mincost[v]))
                v=u;
        }
        if(v==-1)
            break;
        vis[v]=true;
        res+=mincost[v];
        for(int u=0;u<n;u++)
            mincost[u]=min(mincost[u],cost[v][u]);
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    memset(cost,0x3f,sizeof(cost));
    while(m--)
    {
        int i,j,k;
        cin>>i>>j>>k;
        sum+=k;//计算边权和
        cost[i][j]=cost[j][i]=min(k,min(cost[i][j],cost[j][i]));
    }
    cout<<sum-prim();
    return 0;
}

AC代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5002,INF=0x3f3f3f3f;
struct node
{
    int u,v,w;
}e[MAXN],ans[MAXN];
int fa[MAXN],n,m,tot,sum1,sum2;
void init_set()
{
    for(int i=1;i<=n;i++)
        fa[i]=i;
}
int find_set(int x)
{
    if(x==fa[x])
        return x;
    return fa[x]=find_set(fa[x]);
}
void merge_set(int x,int y)
{
    x=find_set(x),y=find_set(y);
    if(x!=y)
        fa[x]=y;
}
bool cmp1(node x,node y)
{
    return x.w<y.w;
}
bool cmp2(node x,node y)
{
    if(x.u<y.u)
        return 1;
    if(x.u==y.u&&x.v<y.v)
        return 1;
    return 0;
}
void kruskal()
{
    stable_sort(e+1,e+m+1,cmp1);
    init_set();
    for(int i=1;i<=m;i++)
    {
        if(find_set(e[i].u)!=find_set(e[i].v))
        {
            ans[++tot]=e[i];
            merge_set(e[i].u,e[i].v);
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        sum1+=c;//计算边权和
        if(a>b)
            swap(a,b);
        e[i].u=a,e[i].v=b,e[i].w=c;
    }
    kruskal();
    sort(ans+1,ans+tot+1,cmp2);
    for(int i=1;i<=tot;i++)
        sum2+=ans[i].w;//计算最小生成树的大小
    cout<<sum1-sum2;
    return 0;
}