网络分析、超级胶水(参照acwing的yxc)

网络分析小明正在做一个网络实验。他设置了 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输入样例14 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输出样例113 13 5 3代码1超时import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int N100010; static int inf[]new int[N]; static int p[]new int[N]; //qq public static void main(String []args) throws IOException{ // System.out.println(1); BufferedReader brnew BufferedReader(new InputStreamReader(System.in)); //int nInteger.parseInt(br.readLine()); String g[]br.readLine().split( ); int nInteger.parseInt(g[0]),mInteger.parseInt(g[1]); for (int i 1; i n; i) { p[i]i; } for (int i 0; i m; i) { gbr.readLine().split( ); int pefixInteger.parseInt(g[0]),aInteger.parseInt(g[1]),bInteger.parseInt(g[2]); if(pefix1){ if(ab)continue; union(a,b); }else{ int parentfind(a); for (int j 1; j n; j) { if(find(j)parent)inf[j]b; } } } StringBuilder stringBuildernew StringBuilder(); for (int i 1; i n; i) { stringBuilder.append(inf[i] ); } System.out.println(stringBuilder.toString().trim()); } static void union(int a,int b){ p[find(a)]find(b); } static int find(int a){ if(a!p[a]){ p[a]find(p[a]); } return p[a]; } }代码2import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main {//a指向b inf(a)-inf(b) static int N100010; static int inf[]new int[N]; static int p[]new int[N]; //qq public static void main(String []args) throws IOException{ //System.out.println(1); BufferedReader brnew BufferedReader(new InputStreamReader(System.in)); //int nInteger.parseInt(br.readLine()); String g[]br.readLine().split( ); int nInteger.parseInt(g[0]),mInteger.parseInt(g[1]); for (int i 1; i n; i) { p[i]i; } for (int i 0; i m; i) { gbr.readLine().split( ); int pefixInteger.parseInt(g[0]),aInteger.parseInt(g[1]),bInteger.parseInt(g[2]); if(pefix1){ afind(a);bfind(b); if(ab)continue; p[a]b; inf[a]-inf[b]; }else{ afind(a); inf[a]b; } } StringBuilder stringBuildernew StringBuilder(); for (int i 1; i n; i) { if(ifind(i))stringBuilder.append(inf[i] ); //输出时 每个节点都要进行一次find else{ stringBuilder.append(inf[i]inf[find(i)] ); } } System.out.println(stringBuilder.toString().trim()); } static int find(int x) { if (p[x] x || p[x] p[p[x]]) return p[x]; int r find(p[x]); // 关键 inf[x] inf[p[x]]; p[x] r; return r; } }代码3import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main {//建立新节点 static int N100010; static int inf[]new int[N]; static int p[]new int[N]; //qq public static void main(String []args) throws IOException{ //System.out.println(1); BufferedReader brnew BufferedReader(new InputStreamReader(System.in)); //int nInteger.parseInt(br.readLine()); String g[]br.readLine().split( ); int nInteger.parseInt(g[0]),mInteger.parseInt(g[1]); for (int i 1; i N-1; i) {//一定要是大N p[i]i; } int kn; for (int i 0; i m; i) { gbr.readLine().split( ); int pefixInteger.parseInt(g[0]),aInteger.parseInt(g[1]),bInteger.parseInt(g[2]); if(pefix1){ afind(a);bfind(b); if(ab)continue; p[a]p[b]k; }else{ afind(a); inf[a]b; } } StringBuilder stringBuildernew StringBuilder(); for (int i 1; i n; i) { if(ifind(i))stringBuilder.append(inf[i] ); else{ stringBuilder.append(inf[i]inf[find(i)] ); } } System.out.println(stringBuilder.toString().trim()); } static int find(int x) { if (p[x] x || p[x] p[p[x]]) return p[x]; int r find(p[x]); // 关键 inf[x] inf[p[x]]; p[x] r; return r; } }超级胶水小明有 n 颗石子按顺序摆成一排。他准备用胶水将这些石子粘在一起。每颗石子有自己的重量如果将两颗石子粘在一起将合并成一颗新的石子重量是这两颗石子的重量之和。为了保证石子粘贴牢固粘贴两颗石子所需要的胶水与两颗石子的重量乘积成正比本题不考虑物理单位认为所需要的胶水在数值上等于两颗石子重量的乘积。每次合并小明只能合并位置相邻的两颗石子并将合并出的新石子放在原来的位置。现在小明想用最少的胶水将所有石子粘在一起请帮助小明计算最少需要多少胶水。输入格式输入的第一行包含一个整数 n表示初始时的石子数量。第二行包含 n 个整数 w1,w2,…,wn依次表示每颗石子的重量。输出格式一个整数表示答案。数据范围1≤n≤105,1≤wi≤1000输入样例13 3 4 5输出样例147输入样例28 1 5 2 6 3 7 4 8输出样例2546代码import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int N100010; //qq public static void main(String []args) throws IOException{ // System.out.println(1); BufferedReader brnew BufferedReader(new InputStreamReader(System.in)); int nInteger.parseInt(br.readLine()); String g[]br.readLine().split( ); //int nInteger.parseInt(g[0]),mInteger.parseInt(g[1]); //枚举之后 我们会发现 任意合并方式 的代价之和是 任意两个元素乘积之和 long sum0,res0;//我们每次合并前两堆 sum表示每次合并第一堆的重量 res结果 for (int i 0; i g.length; i) { ressum*Integer.parseInt(g[i]); sumInteger.parseInt(g[i]); } System.out.println(res); } }