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>
using namespace std;
#define N 1024
#define int long long
#define all(x) begin(x),end(x)
vector<tuple<int,int,int>>tp;
vector<int>adj[N];
vector<tuple<int,int,int>> goth[N];
int dep[N],dp[N][N],p[N],ti[N],to[N],cnt;
void dfs(int n){
ti[n]=++cnt;
if(p[n])adj[n].erase(find(all(adj[n]),p[n]));
for(auto i:adj[n])
p[i]=n,dep[i]=dep[n]+1,dfs(i);
to[n]=cnt;
}
int lca(int a,int b) {
while(!(ti[a]<=ti[b]&&to[b]<=to[a]))
a=p[a];
return a;
}
void calcdp(int n){
for(auto i:adj[n])
calcdp(i);
int sz=goth[n].size();
vector<tuple<int,int,int>>details(sz,{0,10,10});
for(int i=0;i<sz;i++) {
auto[a,b,c]=goth[n][i];
int S3=c;
if(a-n) S3+=dp[a][0];
if(b-n) S3+=dp[b][0];
while(a!=n)
if(p[a]==n)
get<1>(details[i])=find(all(adj[n]),a)-adj[n].begin(),a=n;
else S3+=dp[p[a]][1<<find(all(adj[p[a]]),a)-adj[p[a]].begin()],a=p[a];
while(b!=n)
if(p[b]==n)
get<2>(details[i])=find(all(adj[n]),b)-adj[n].begin(),b=n;
else S3+=dp[p[b]][1<<find(all(adj[p[b]]),b)-adj[p[b]].begin()],b=p[b];
get<0>(details[i])=S3;
}
int bits=adj[n].size();
for(int i=1<<bits;i--;){
for(int j=0;j<bits;j++)
dp[n][i]+=(~i>>j&1)*dp[adj[n][j]][0];
for(auto[a,b,c]:details) if(~i>>b&1&&~i>>c&1)
dp[n][i]=max(dp[n][i],a+dp[n][i|1<<b|1<<c]);
}
}
signed main(){
int n,m,W=0;
cin>>n>>m;
for(int i=0;i<m;i++){
int a,b,c;
cin>>a>>b>>c;
if(!c) adj[a].push_back(b),
adj[b].push_back(a);
else tp.push_back({a,b,c});
W+=c;
}
dfs(1);
for(auto [a,b,w]:tp)
if(~(dep[a]+dep[b])&1)
goth[lca(a,b)].push_back({a,b,w});
calcdp(1);
cout<<W-*dp[1];
}
Compilation message (stderr)
training.cpp: In function 'void calcdp(long long int)':
training.cpp:35:56: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
35 | else S3+=dp[p[a]][1<<find(all(adj[p[a]]),a)-adj[p[a]].begin()],a=p[a];
| ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
training.cpp:39:56: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
39 | else S3+=dp[p[b]][1<<find(all(adj[p[b]]),b)-adj[p[b]].begin()],b=p[b];
| ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
# | 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... |
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |