#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long
#define pr pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vi2 vector<vector<int>>
#define vc vector<char>
#define vs vector<string>
#define vip vector<pair<int,int>>
#define rep(n) for(int i=0;i<n;i++)
#define repj(i,n) for(int j=i;j<n;j++)
#define st(a,n) sort(a,a+n)
#define stv(a) sort(a.begin(),a.end())
#define rstv(a) sort(a.rbegin(),a.rend())
#define pb(a) push_back(a)
#define endl '\n'
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define bp(i)int __builtin_popcount(i)
vector<pair<int,pair<int,int>>> adj;
vector<pair<int,pair<int,int>>> adj1;
vector<vector<pair<int,int>>> mst;
vector<int> parent;
vector<int> sz;
vector<vector<int>> up(2e5+5,vector<int>(20,0));
vector<int> depth;
vector<int> mxweight;
int find_parent(int v){
if(v==parent[v]){
return v;
}else{
return parent[v]=find_parent(parent[v]);
}
}
void union_set(int u,int v){
int u1=find_parent(u);
int v1=find_parent(v);
if(sz[v]>sz[u]){
swap(u,v);
}
parent[v1]=u1;
sz[u1]+=sz[v1];
}
void dfs(int v,int parent){
up[v][0]=parent;
for(int i=1;i<20;i++){
up[v][i]=up[up[v][i-1]][i-1];
}
for(auto ch:mst[v]){
if(ch.fi==parent){
continue;
}
depth[ch.fi]=depth[v]+1;
dfs(ch.fi,v);
mxweight[v]=max(mxweight[v],max(mxweight[ch.fi],ch.se));
}
}
int kthparent(int v,int k){
for(int i=19;i>=0;i--){
if(k&up[v][i]){
v=up[v][i];
}
}
return v;
}
int lca(int a,int b){
if(depth[b]>depth[a]){
swap(a,b);
}
int climb=depth[a]-depth[b];
a=kthparent(a,climb);
if(a==b){
return a;
}
for(int i=19;i>=0;i--){
if(up[a][i]!=up[b][i]){
a=up[a][i];
b=up[b][i];
}
}
return up[a][0];
}
void solve(){
int n,m;
cin>>n>>m;
adj.resize(m);
adj1.resize(m);
mst.resize(n+1);
sz.resize(n+1,1);
depth.resize(n+1);
parent.resize(n+1);
mxweight.resize(n+1);
for(int i=0;i<=n;i++){
parent[i]=i;
}
for(int i=0;i<m;i++){
int u,v,w;
cin>>u>>v>>w;
adj[i].fi=w;
adj[i].se.fi=u;
adj[i].se.se=v;
adj1[i].fi=w;
adj1[i].se.fi=u;
adj1[i].se.se=v;
}
stv(adj);
int weight=0;
for(int i=0;i<m;i++){
int w=adj[i].fi;
int u=adj[i].se.fi;
int v=adj[i].se.se;
if(find_parent(u)==find_parent(v)){
continue;
}else{
union_set(u,v);
weight+=w;
mst[u].push_back({v,w});
mst[v].push_back({u,w});
}
}
dfs(1,0);
for(int i=0;i<m;i++){
int w=adj1[i].fi;
int u=adj1[i].se.fi;
int v=adj1[i].se.se;
cout<<weight<<" "<<w<<" "<<lca(u,v)<<endl;
}
}
int32_t main(){
fastio;
int t;
t=1;
while(t--){
solve();
}
return 0;
}
Write, Run & Share C++ code online using OneCompiler's C++ online compiler for free. It's one of the robust, feature-rich online compilers for C++ language, running on the latest version 17. Getting started with the OneCompiler's C++ compiler is simple and pretty fast. The editor shows sample boilerplate code when you choose language as C++ and start coding!
OneCompiler's C++ online compiler supports stdin and users can give inputs to programs using the STDIN textbox under the I/O tab. Following is a sample program which takes name as input and print your name with hello.
#include <iostream>
#include <string>
using namespace std;
int main()
{
string name;
cout << "Enter name:";
getline (cin, name);
cout << "Hello " << name;
return 0;
}
C++ is a widely used middle-level programming language.
When ever you want to perform a set of operations based on a condition If-Else is used.
if(conditional-expression) {
//code
}
else {
//code
}
You can also use if-else for nested Ifs and If-Else-If ladder when multiple conditions are to be performed on a single variable.
Switch is an alternative to If-Else-If ladder.
switch(conditional-expression){
case value1:
// code
break; // optional
case value2:
// code
break; // optional
......
default:
code to be executed when all the above cases are not matched;
}
For loop is used to iterate a set of statements based on a condition.
for(Initialization; Condition; Increment/decrement){
//code
}
While is also used to iterate a set of statements based on a condition. Usually while is preferred when number of iterations are not known in advance.
while (condition) {
// code
}
Do-while is also used to iterate a set of statements based on a condition. It is mostly used when you need to execute the statements atleast once.
do {
// code
} while (condition);
Function is a sub-routine which contains set of statements. Usually functions are written when multiple calls are required to same set of statements which increases re-usuability and modularity. Function gets run only when it is called.
return_type function_name(parameters);
function_name (parameters)
return_type function_name(parameters) {
// code
}