This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ff first
#define ss second
#define tcT template<class T
#define fastio ios::sync_with_stdio(false);cin.tie(nullptr);
#define ln '\n'
#define nwln cout<<ln;
using namespace std;
tcT> using vr = vector<T>;
using pi = pair<int, int>;
using vi = vr<int>;
using vpi = vr<pi>;
using ll = long long;
using oo = bool;
#define maxs(i, j) (i = max(i, j))
#define fri(i,a,b) for(int i=(a); i<(b); ++i)
#define each(x, a) for(auto& x: a)
#define sz(x) int((x).size())
#define phb push_back
#define eb emplace_back
const int MX = (int) 3e5+3;
ll N, M, ans;
oo used[MX];
set<int> orz[MX];
vpi adj[MX];
inline void dfs(int u) {
used[u] = true;
ll res = 0, xam = 0, U, idx = 0;
map<int, int> cur;
each(x, adj[u]) {
cur[x.ff] = idx++;
res += x.ss;
if(xam < x.ss) U = x.ff, xam = x.ss;
}
maxs(ans, res);
// idk if this "if" is necessary
if(!used[U]) {
each(x, adj[U]) {
if(!orz[u].count(x.ff)) continue;
maxs(ans, xam + x.ss + adj[u][cur[x.ff]].ss);
}
}
each(x, adj[u]) {
if(!used[x.ff]) dfs(x.ff);
}
}
int main()
{
fastio
cin>>N>>M;
while(M--) {
int u, v, w;
cin>>u>>v>>w;
adj[u].eb(v, w);
adj[v].eb(u, w);
orz[u].insert(v);
orz[v].insert(u);
}
fri(i,1,N+1) {
if(used[i]) continue;
dfs(i);
}
cout<<ans<<ln;
return 0;
}
/*
Wow, beautiful trick
Two possible types: star or triangle
Stars are easy, bottleneck are the triangles
What I do is, if I'm on node v then between all its edges I choose the
greatest one and try to match the rest... it can be proved it's correct
Suppose the answer is not correct and let the max-weight triangle be
p, q -> a
q, r -> b
r, p -> c
Then, we're assuming there exists
p, P -> greater than c, a but less than b
q, Q -> greater than a, b but less than c
r, R -> greater than b, c but less than a
Contradiction! We're done :D
*/
Compilation message (stderr)
pigus_skrydziai.cpp: In function 'void dfs(int)':
pigus_skrydziai.cpp:35:23: warning: 'U' may be used uninitialized in this function [-Wmaybe-uninitialized]
35 | ll res = 0, xam = 0, U, idx = 0;
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |