首页 > 其他分享 >蓝桥杯-网络分析

蓝桥杯-网络分析

时间:2023-01-19 10:35:39浏览次数:43  
标签:int scanf find 蓝桥 fa 网络分析 节点 define

网络分析

小明正在做一个网络实验。

他设置了 n 台电脑,称为节点,用于收发和存储数据。

初始时,所有节点都是独立的,不存在任何连接。

小明可以通过网线将两个节点连接起来,连接后两个节点就可以互相通信了。

两个节点如果存在网线连接,称为相邻。

小明有时会测试当时的网络,他会在某个节点发送一条信息,信息会发送到每个相邻的节点,之后这些节点又会转发到自己相邻的节点,直到所有直接或间接相邻的节点都收到了信息。

所有发送和接收的节点都会将信息存储下来。

一条信息只存储一次。

给出小明连接和测试的过程,请计算出每个节点存储信息的大小。

输入格式
输入的第一行包含两个整数 n,m,分别表示节点数量和操作数量。

节点从 1 至 n 编号。

接下来 m 行,每行三个整数,表示一个操作。

如果操作为 1 a b,表示将节点 a 和节点 b 通过网线连接起来。当 a = b 时,表示连接了一个自环,对网络没有实质影响。
如果操作为 2 p t,表示在节点 p 上发送一条大小为 t 的信息。
输出格式
输出一行,包含 n 个整数,相邻整数之间用一个空格分割,依次表示进行完上述操作后节点 1 至节点 n 上存储信息的大小。

数据范围
\(1≤n≤10000,\)
\(1≤m≤105,\)
\(1≤t≤100\)
输入样例1:

4 8
1 1 2
2 1 10
2 3 5
1 4 1
2 2 2
1 1 2
1 2 4
2 2 1

输出样例1:

13 13 5 3

dfs暴力做法

该方法可以拿70%的分数,适合骗分

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = a;i < b;i++)
#define per(i,a,b) for(int i = b - 1;i >= a;i--)
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;

const int N = 10010;

int cnt[N], n, m;
bool vis[N];
VI G[N];

void dfs(int u, int t) {
    vis[u] = 1;
    cnt[u] += t;
    for(auto v : G[u]) {
        if(vis[v]) continue;
        dfs(v,t);
    }
}

int main() {
    scanf("%d%d", &n, &m);
    rep(_,0,m) {
        int op;
        scanf("%d", &op);
        if(op ==  1) {
            int a, b;
            scanf("%d%d", &a, &b);
            G[a].push_back(b);
            G[b].push_back(a);
        }else {
            int p, t;
            scanf("%d%d", &p, &t);
            memset(vis,0,sizeof(vis));
            dfs(p,t);
        }
    }
    rep(i,1,n+1) printf("%d ", cnt[i]);
    puts("");
    return 0;
}

正解:并查集的高级操作

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = a;i < b;i++)
#define per(i,a,b) for(int i = b - 1;i >= a;i--)
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;

const int N = 10010;

int fa[N], d[N], n, m;
int find(int x) {
    if(x == fa[x] || fa[fa[x]] == fa[x]) return fa[x];
    int t = find(fa[x]);
    d[x] += d[fa[x]];
    fa[x] = t;
    return fa[x];
}


int main() {
    scanf("%d%d", &n, &m);
    rep(i,1,n+1) fa[i] = i;
    rep(_,0,m) {
        int op; 
        scanf("%d", &op);
        if(op ==  1) {
            int a, b;
            scanf("%d%d", &a, &b);
            int fx = find(a), fy = find(b);
            if(fx != fy) {
                d[fx] -= d[fy];
                fa[fx] = fy;
            }
        }else {
            int p, t;
            scanf("%d%d", &p, &t);
            d[find(p)] += t;
        }
    }
    rep(i,1,n+1) {
        if(i == find(i)) printf("%d ", d[i]);
        else printf("%d ", d[i] + d[find(i)]);
    }
    puts("");
    return 0;
}

标签:int,scanf,find,蓝桥,fa,网络分析,节点,define
From: https://www.cnblogs.com/junlin623/p/17061122.html

相关文章

  • 12届蓝桥杯javab组真题
    12届蓝桥杯javab组真题A,ASC签到题packagetrain;publicclasstest_5{publicstaticvoidmain(String[]args){System.out.println('L'+0);}}B,卡片此题......
  • SMU冬训营第二周蓝桥杯模拟赛
    A.解码题目:小明有一串很长的英文字母,可能包含大写和小写。在这串字母中,有很多连续的是重复的。小明想了一个办法将这串字母表达得更短:将连续的几个相同字母写成字母+......
  • P8723 [蓝桥杯 2020 省 AB3] 乘法表
    题目描述九九乘法表是学习乘法时必须要掌握的。在不同进制数下,需要不同的乘法表。例如,四进制下的乘法表如下所示:1*1=12*1=22*2=103*1=33*2=123*3=21请注意,乘......
  • P8716 [蓝桥杯 2020 省 AB2] 回文日期
    题目描述2020年春节期间,有一个特殊的日期引起了大家的注意:2020年2月2日。因为如果将这个日期按 yyyymmdd 的格式写成一个 88 位数是 20200202,恰好是一个回文......
  • 蓝桥杯学习
    1,九进制转换成十进制做错题了,但是也是简单的签到题, importjava.util.Scanner;publicclassMain{publicstaticvoidmain(String[]args){......
  • 蓝桥杯 X进制减法
    题目描述进制规定了数字在数位上逢几进一。X进制是一种很神奇的进制,因为其每一数位的进制并不固定!例如说某种X进制数,最低数位为二进制,第二数位为十进制,第三数位为......
  • 2014蓝桥
    中国古代文献中,曾记载过“大衍数列”,主要用于解释中国传统文化中的太极衍生原理。它的前几项是:0、2、4、8、12、18、24、32、40、50...其规律是:对偶数项,是序号平方再......
  • 蓝桥杯 修剪灌木
    题目描述爱丽丝要完成一项修剪灌木的工作。有N棵灌木整齐的从左到右排成一排。爱丽丝在每天傍晚会修剪一棵灌木,让灌木的高度变为0厘米。爱丽丝修剪灌木的顺序是从......
  • 第12届蓝桥杯JavaB组省赛
    第12届蓝桥杯JavaB组省赛前言用时及分数自测开始时间:\(2023年1月11日16:00\)自测结束时间:\(2023年1月11日18:05\)自测用时:约\(2\)小时最终得分:\(20(35)\)PS:此处......
  • 蓝桥杯-交换瓶子
    交换瓶子(第七届蓝桥杯省赛JAVAA组)有N个瓶子,编号1∼N,放在架子上。比如有5个瓶子:21354要求每次拿起2个瓶子,交换它们的位置。经过若干次后,使得瓶子的序......