首页 > 其他分享 >AcWing1141. 局域网

AcWing1141. 局域网

时间:2022-12-25 22:44:07浏览次数:66  
标签:AcWing1141 连通性 int qquad 局域网 权值 include 总和

传送门

题目大意

\(\qquad\)给定一张无向图,没有重边和自环,要删去一些边但是仍然要保证图的连通性,求这些边边权总和的最大值。

解题思路

\(\qquad\)我们不一定要真的去统计它的最大值,因为所有边的权值总和是不变的,所以我们算出来保留的边的权值总和越小,删掉的边的权值总和越大。
\(\qquad\)如果是统计保留的边,那保证连通性就简单多了,我们可以用到最小生成树,这里采用Kruskal算法,因为好写Kruskal要用到并查集,别忘记初始化

代码

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

using namespace std;

const int N = 11000, M = 22000;
int p[N], n, m;

struct Edge {
    int u, v, w;
    bool operator <(const Edge& W) const {
        return w < W.w;
    }
} edge[N];

int find(int x) 
{
    if (x != p[x]) p[x] = find(p[x]);
    return p[x];
}

int Krus() 
{
    sort(edge + 1, edge + 1 + m);
    
    int res = 0;
    for (int i = 1; i <= m;  i ++ ) 
    {
        int fu = find(edge[i].u), fv = find(edge[i].v);
        
        if (fu == fv) continue ;
        else {
            p[fu] = fv;
            res += edge[i].w;
        }
    }
    
    return res;
}

int main() 
{
    scanf("%d%d", &n, &m);
    
    int sum = 0;
    for (int i = 1; i <= m; i ++ ) 
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        edge[i] = {u, v, w}, p[i] = i;
        sum += w;
    }
    
    printf("%d\n", sum - Krus());
    
    return 0;
}

\(\color{Green}{顺利AC!}\)

标签:AcWing1141,连通性,int,qquad,局域网,权值,include,总和
From: https://www.cnblogs.com/StkOvflow/p/17004803.html

相关文章

  • 局域网内手机如何播放电脑上的视频文件?
    最近下班后没什么事,就想着看看电影、电视剧啥的。因为之前这些视频都是放到移动硬盘上的,用电脑看没什么问题,只需连接电脑的USB口就行了。但如果想用手机看的话,就麻烦些。也......
  • 内网直播局域网直播校园直播系统方案,播控管理
    音视频融合应用系统​方案2022/11/03 目录第1章项目概况...11.1需求背景...11.2建设的必要性...11.3项目建设具备的基础条件...11.4建设内容...2第2章系统介......
  • 内网直播局域网直播系统的搭建
    搭建一套完全本地化部署的流媒体直播点播系统,引入本地演播室,录播,报告厅、会议,电视节目等实时信号,实现本地网络的手机、PC、机顶盒等智能终端进行观看。系统集成直播,点播,录制......
  • 局域网直播内网直播系统的搭建
    搭建一套完全本地化部署的局域网流媒体直播点播系统,引入本地演播室,录播,报告厅、会议,电视节目等实时信号,实现本地网络的手机、PC、机顶盒等智能终端进行观看。系统集成直播,......
  • unity 局域网内传送照片
    发送的电脑usingUnityEngine;usingSystem.Collections;usingSystem.Net;usingSystem.Net.Sockets;usingSystem.IO;usingSystem;publicclassSendPhoto:Mon......
  • 局域网 大文件分片上传处理
    ​ HTML部分 <%@ Page Language="C#" AutoEventWireup="true" CodeBehind="index.aspx.cs" Inherits="up6.index" %><!DOCTYPE html PUBLIC "-//W3C//DTDXH......
  • 传统局域网上层管理地址互通
     2022.12.13--0.37传统局域网上层管理地址互通1、网络结构设备:AR2200路由器;USG6000V防火墙;CE6800交换机步骤:1、配置路由器地址;2、配置防火墙地址,与路由器对接口需......
  • 非局域网远程访问MySQL
    使用内网穿透解决,市面上说道最多的是“花生壳”主要操作见这篇官方说明但其中提到的什么花生棒(第二、三点)完全不用管,应该算是产品推销。登录后选“新增内网映射”进入......
  • 计算机网络--局域网-上
    MAC地址:MAC地址(LAN地址,局域网地址),用于局域网内标识一个帧从哪个接口发出,到达哪个物理相连的其他接口;每块网卡都有唯一的MAC地址,48位,通常固定在网卡的ROM......
  • Debian11.5 最小化安装后更改主机名、安装桌面、设置默认语言、时区、静态IP、局域网D
    最小化安装,指的是采用debian-11.5.0-amd64-netinst.iso382.0MiB2022-09-1020:40这个只有382M的镜像,仅安装了ssh服务的状态,只占了900多M磁盘空间。如果使用Live......