fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define maxn 100005
  4. #define lgn 20
  5. #define pb emplace_back
  6. #define mem(x,y) memset(x,y,sizeof x)
  7. typedef long long ll;
  8. #define io ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  9. ll n,m,total;
  10. struct Edge{
  11. 	ll from,to,w;
  12. };
  13. struct edge{
  14. 	ll to,w;
  15. };
  16. struct djs{
  17. 	ll f[maxn];
  18. 	void init(){for(ll i=1;i<=n;i++)f[i]=i;}
  19. 	ll find(ll x){return x==f[x]?x:f[x]=find(f[x]);}
  20. 	bool same(ll x,ll y){return find(x)==find(y);}
  21. 	void Union(ll x,ll y){f[find(x)]=find(y);}
  22. };
  23. vector<Edge> mst;
  24. vector<Edge> non;
  25. vector<edge> adj[maxn];
  26. ll d[maxn];
  27. ll pa[lgn+1][maxn];
  28. ll mx[lgn+1][maxn];
  29. bool operator<(const Edge &a,const Edge &b){
  30. 	return a.w<b.w;
  31. }
  32. void kruskal(){
  33. 	djs ds;ds.init();
  34. 	for(ll i=0;i<m;i++){
  35. 		if(!ds.same(mst[i].from,mst[i].to)){
  36. 			total+=mst[i].w;
  37. 			ds.Union(mst[i].from,mst[i].to);
  38. 			adj[mst[i].from].pb(edge{mst[i].to,mst[i].w});
  39. 			adj[mst[i].to].pb(edge{mst[i].from,mst[i].w});
  40. 		}
  41. 		else non.pb(mst[i]);
  42. 	}
  43. }
  44. void dfs(ll index,ll fa,ll dis){
  45. 	d[index]=dis;
  46. 	pa[0][index]=fa;
  47. 	for(auto i:adj[index]){
  48. 		if(i.to==fa)continue;
  49. 		mx[0][i.to]=i.w;
  50. 		dfs(i.to,index,dis+1);
  51. 	}
  52. }
  53. void build(){
  54. 	for(ll i=1;i<=lgn;i++){
  55. 		for(ll j=1;j<=n;j++){
  56. 			pa[i][j]=pa[i-1][pa[i-1][j]];
  57. 			mx[i][j]=max(mx[i-1][j],mx[i-1][mx[i-1][j]]);
  58. 		}
  59. 	}
  60. }
  61. ll LCA(ll u,ll v){
  62. 	ll maxium=0;
  63. 	if(d[u]<d[v])swap(u,v);
  64. 	ll s=d[u]-d[v];
  65. 	for(ll i=lgn;i>=0;i--){
  66. 		if((s>>i)&1){
  67. 			maxium=max(maxium,mx[i][u]);
  68. 			u=pa[i][u];
  69. 		}
  70. 	}
  71. 	if(u==v)return maxium;
  72. 	for(ll i=lgn;i>=0;i--){
  73. 		if(pa[i][u]!=pa[i][v]){
  74. 			maxium=max({maxium,mx[i][u],mx[i][v]});
  75. 			u=pa[i][u];
  76. 			v=pa[i][v];
  77. 		}
  78. 	}
  79. 	maxium=max({maxium,mx[0][u],mx[0][n]});
  80. 	return maxium;
  81. }
  82. int main(){
  83. 	io;
  84. 	while(cin>>n>>m){
  85. 		//init(mem)
  86. 		mst.clear();
  87. 		non.clear();
  88. 		for(ll i=0;i<n;i++)adj[i].clear();
  89. 		total=0;
  90. 		mem(d,-1);
  91. 		mem(mx,0);
  92. 		mem(pa,-1);
  93.  
  94. 		for(ll i=0;i<m;i++){
  95. 			ll a,b,c;
  96. 			cin>>a>>b>>c;
  97. 			mst.pb(Edge{a,b,c});
  98. 		}
  99. 		sort(mst.begin(),mst.end());
  100. 		kruskal();
  101. 		dfs(1,0,0);
  102. 		build();
  103. 		ll ans=LONG_LONG_MAX;
  104. 		for(ll i=0;i<ll(non.size());i++){
  105. 			ll lca=LCA(non[i].from,non[i].to);
  106. 			ans=min(ans,total-lca+non[i].w);
  107. 		}
  108. 		cout<<total<<' '<<ans<<endl;
  109. 	}
  110. 	return 0;
  111. }
Success #stdin #stdout 0s 51184KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/XrkGUJ
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!