数据结构与算法题目集(中文) - 7-50 畅通工程之局部最小花费问题(35 分)

简介: 数据结构与算法题目集(中文) - 7-50 畅通工程之局部最小花费问题(35 分)

题目链接:点击打开链接

题目大意:略。

解题思路:Kruskal 算法 + 首先要将已经修建的道路进行并查集合并操作,用 set 存集合中结点的个数来判断是否所有点都已经操作完成,剩余的点按照基本操作进行就好了。

AC 代码


#include<bits/stdc++.h>
#include<cmath>
#define mem(a,b) memset(a,b,sizeof a);
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn=110;
struct edge
{
    int u,v,w,f;
}es[maxn*maxn];
int n,m;
int pre[maxn];
set<int> st; // 判断是否所有点都已经操作完成
void init()
{
    st.clear();
    m=n*(n-1)/2;
    for(int i=1;i<=n;i++) pre[i]=i;
}
int cmp(edge e1,edge e2)
{
    if(e1.f==e2.f) return e1.w<e2.w;
    return e1.f>e2.f;
}
int find(int x)
{
    return pre[x]==x ? x : pre[x]=find(pre[x]);
}
int kruskal()
{
    int ans=0,fu,fv;
    for(int i=0;i<m;i++)
    {
        fu=find(es[i].u), fv=find(es[i].v);
        st.insert(es[i].u); st.insert(es[i].v);
        if(es[i].f==1)
        {
            pre[fu]=fv;
        }
        else if(fu!=fv)
        {
            ans+=es[i].w;
            pre[fu]=fv;
        }
        if(st.size()==n) break;
    }
    printf("%d\n",ans);
}
int main()
{
    while(~scanf("%d",&n))
    {
        init();
        for(int i=0;i<m;i++)
            scanf("%d%d%d%d",&es[i].u,&es[i].v,&es[i].w,&es[i].f);
        sort(es,es+m,cmp); // 因为 Kruskal 算法是按照边从小到大选择
        kruskal();
    }
    return 0;
}
目录
相关文章
|
6月前
|
存储 SQL 算法
LeetCode题目113:多种算法实现 路径总和ll
LeetCode题目113:多种算法实现 路径总和ll
|
2月前
|
存储 C语言
栈和队列题目练习
栈和队列题目练习
20 0
|
4月前
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
55 6
|
6月前
|
算法
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
|
5月前
|
机器学习/深度学习 运维 算法
Python基于局部离群因子LOF算法(LocalOutlierFactor)实现信用卡数据异常值检测项目实战
Python基于局部离群因子LOF算法(LocalOutlierFactor)实现信用卡数据异常值检测项目实战
112 0
|
5月前
|
机器学习/深度学习 算法 调度
|
6月前
|
人工智能 算法 搜索推荐
蓝桥杯宝藏排序题目算法(冒泡、选择、插入)
以下是内容的摘要: 本文介绍了三种排序算法:冒泡排序、选择排序和插入排序。冒泡排序通过不断交换相邻的逆序元素逐步排序,最坏情况下需要 O(n^2) 次比较。选择排序在每轮中找到剩余部分的最小元素并放到已排序序列的末尾,同样具有 O(n^2) 时间复杂度。插入排序则是将每个元素插入到已排序序列的正确位置,时间复杂度也是 O(n^2),但空间复杂度为 O(1)。
|
6月前
|
算法
【经典LeetCode算法题目专栏分类】【第11期】递归问题:字母大小写全排列、括号生成
【经典LeetCode算法题目专栏分类】【第11期】递归问题:字母大小写全排列、括号生成
|
6月前
|
算法
【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集:括号生成、岛屿问题、扫雷游戏
【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集:括号生成、岛屿问题、扫雷游戏