#include<bits/stdc++.h>
#define y1 y3647
#define INF 1000000000
#define LL long long
#define pii pair<int,int>
using namespace std;
long long read(){
long long x=0;int f=1;char ch=getchar();
while(ch!=45&&(ch<'0'||ch>'9'))ch=getchar();
if(ch==45){f=-1,ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*=f;
}
template<typename T>T&read(T&x){return x=read();}
template<typename T,typename W>T&cmin(T&a,const W&b){return a>b?(a=b):a;}
template<typename T,typename W>T&cmax(T&a,const W&b){return a<b?(a=b):a;}
const int N=1005,M=5005;
int n,m,t,sum;
int dp[N][M],a[M][3],fa[N],dis[N],vis[N],mp[N][N],dep[N],ed[M][2];
vector<int> e[N],b[N],c[N];
void dfs(int u){
sort(e[u].begin(),e[u].end());
for(auto v:e[u]){
if(fa[u]==v)continue;
fa[v]=u;dis[v]=dis[u]^1;dep[v]=dep[u]+1;
dfs(v);
}
}
pair<int,int> lca(int u,int v){
if(dep[v]>dep[u])swap(u,v);
while(dep[u]!=dep[v]&&fa[u]!=v)u=fa[u];
if(fa[u]==v)return make_pair(u,v);
while(fa[u]!=fa[v])u=fa[u],v=fa[v];
return make_pair(u,v);
}
int _lca(int u,int v){
if(dep[u]==dep[v])return fa[u];
return dep[u]>dep[v]?v:u;
}
void DFS(int now,vector<int> &a,int rt){
if(now==a.size()){
int tot=0;
for(auto v:a){
if(vis[v]==n+1)tot+=mp[rt][v];
else if(v<vis[v])tot+=mp[v][vis[v]];
}
cmax(sum,tot);
return ;
}
if(vis[a[now]])return DFS(now+1,a,rt);
for(int i=now+1;i<a.size();i++)if(!vis[a[i]]){
vis[a[now]]=a[i],vis[a[i]]=a[now];
DFS(now+1,a,rt);
vis[a[now]]=vis[a[i]]=0;
}
vis[a[now]]=n+1;
DFS(now+1,a,rt);
vis[a[now]]=0;
}
int solve_basic(vector<int> a,int u){
sum=0;
DFS(0,a,u);
return sum;
}
void solve(int u){
// for(auto w:e[u])printf("%d ",w);puts("");
if(u!=1)e[u].erase(lower_bound(e[u].begin(),e[u].end(),fa[u]));
for(auto v:e[u])
solve(v),mp[u][v]=mp[v][u]=dp[v][0];
for(auto w:c[u]){
int s1=ed[w][0],s2=ed[w][1];
cmax(mp[s1][s2],(s1!=u?dp[s1][w]:0)+(s2!=u?dp[s2][w]:0)+a[w][2]);
mp[s2][s1]=mp[s1][s2];
}
dp[u][0]=solve_basic(e[u],u);
for(int i=0;i<e[u].size();i++){
int v=e[u][i];auto tp=e[u];
tp.erase(lower_bound(tp.begin(),tp.end(),v));
int val=solve_basic(tp,u);
for(int j=1;j<=m;j++)if(~dp[v][j])dp[u][j]=val+dp[v][j];
}
for(auto v:b[u])dp[u][v]=dp[u][0];
}
void ___solve(){
int i,j,ans=0;
read(n),read(m);
for(i=1;i<=m;i++){
read(a[i][0]),read(a[i][1]),read(a[i][2]);
if(a[i][2]==0)e[a[i][0]].push_back(a[i][1]),e[a[i][1]].push_back(a[i][0]);
}
dfs(1);
for(i=1;i<=m;i++){
if(a[i][2]==0)continue;
if(dis[a[i][0]]^dis[a[i][1]]==0){
tie(ed[i][0],ed[i][1])=lca(a[i][1],a[i][0]);
b[a[i][0]].push_back(i);
b[a[i][1]].push_back(i);
c[_lca(ed[i][0],ed[i][1])].push_back(i);
}
ans+=a[i][2];
}
memset(dp,-1,sizeof(dp));
solve(1);
cout<<ans-dp[1][0]<<endl;
}
signed main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
// freopen(".in","w",stdout);
int tot=1;
// read(tot);
while(tot--){
___solve();
}
return 0;
}
Compilation message
training.cpp: In function 'void DFS(int, std::vector<int>&, int)':
training.cpp:40:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | if(now==a.size()){
| ~~~^~~~~~~~~~
training.cpp:50:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for(int i=now+1;i<a.size();i++)if(!vis[a[i]]){
| ~^~~~~~~~~
training.cpp: In function 'void solve(int)':
training.cpp:75:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for(int i=0;i<e[u].size();i++){
| ~^~~~~~~~~~~~
training.cpp: In function 'void ___solve()':
training.cpp:93:31: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
93 | if(dis[a[i][0]]^dis[a[i][1]]==0){
| ~~~~~~~~~~~~^~~
training.cpp:84:8: warning: unused variable 'j' [-Wunused-variable]
84 | int i,j,ans=0;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
20052 KB |
Output is correct |
| 2 |
Correct |
8 ms |
20052 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
20180 KB |
Output is correct |
| 2 |
Correct |
9 ms |
20308 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
24084 KB |
Output is correct |
| 2 |
Correct |
18 ms |
24232 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
20052 KB |
Output is correct |
| 2 |
Correct |
9 ms |
20052 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
20180 KB |
Output is correct |
| 2 |
Correct |
9 ms |
20220 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
20436 KB |
Output is correct |
| 2 |
Correct |
10 ms |
20436 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
21308 KB |
Output is correct |
| 2 |
Correct |
9 ms |
21332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
22068 KB |
Output is correct |
| 2 |
Correct |
11 ms |
22024 KB |
Output is correct |
| 3 |
Correct |
15 ms |
22100 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
24020 KB |
Output is correct |
| 2 |
Correct |
47 ms |
23872 KB |
Output is correct |
| 3 |
Correct |
16 ms |
23964 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
22020 KB |
Output is correct |
| 2 |
Correct |
12 ms |
22156 KB |
Output is correct |
| 3 |
Correct |
19 ms |
24328 KB |
Output is correct |
| 4 |
Correct |
14 ms |
22072 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
23948 KB |
Output is correct |
| 2 |
Correct |
24 ms |
24180 KB |
Output is correct |
| 3 |
Correct |
36 ms |
24160 KB |
Output is correct |
| 4 |
Correct |
45 ms |
24144 KB |
Output is correct |
