#include <bits/stdc++.h>
#define ll long long
#define db long double
#define N 1005
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
using namespace std;
vector <int> a[N];
struct edge { int u,v,k; };
vector <edge> c[N],add;
ll n,m,i,u,v,sum,f[N],g[N],p[N],h[N],k,num[N][N],w[11],w2[11][11],dp[N][11][1024],nchild[N];
void dfs(int u)
{
for(int i=0;i<a[u].size();i++)
{
int v=a[u][i];
if(v!=p[u]) h[v]=h[u]+1,p[v]=u,dfs(v);
}
}
void opt(ll &a,ll b) { a=max(a,b); }
int LCA(int u,int v)
{
while(h[u]>h[v]) u=p[u];
while(h[v]>h[u]) v=p[v];
while(u!=v) u=p[u],v=p[v];
return u;
}
int nearest(int u,int v)
{
while(p[u]!=v) u=p[u];
return u;
}
ll climb(int u,int v)
{
ll res=0,last;
res+=f[u]; last=u; u=p[u];
while(u!=v)
{
res+=dp[u][nchild[u]-1][((1<<nchild[u])-1)^(1<<num[u][last])];
last=u; u=p[u];
}
return res;
}
void DFS(int u)
{
int i,j,tt;
for(int i=0;i<a[u].size();i++)
{
int v=a[u][i];
if(v!=p[u]) DFS(v);
}
for(int v:a[u])
{
if(v!=p[u]) g[nchild[u]]=f[v],num[u][v]=nchild[u]++;
}
memset(w,0,sizeof(w));
memset(w2,0,sizeof(w2));
for(int i=0;i<c[u].size();i++)
{
edge x=c[u][i];
int v1=x.u,v2=x.v,k=x.k,tg1,tg2;
ll sum,sum1,sum2;
if(v2==u)
{
tg1=num[u][nearest(v1,u)];
opt(w[tg1],climb(v1,u)+k);
}
else
{
tg1=num[u][nearest(v1,u)]; sum1=climb(v1,u);
tg2=num[u][nearest(v2,u)]; sum2=climb(v2,u);
opt(w2[tg1][tg2],sum1+sum2+k);
opt(w2[tg2][tg1],sum1+sum2+k);
}
}
if(nchild[u]==0) return ;
dp[u][0][0]=0;
dp[u][0][1]=max(w[0],g[0]);
for(i=1;i<nchild[u];i++)
{
for(tt=0;tt<(1<<i);tt++)
{
opt(dp[u][i][tt],dp[u][i-1][tt]);
opt(dp[u][i][tt|(1<<i)],dp[u][i-1][tt]+max(g[i],w[i]));
for(j=0;j<i;j++)
if(BIT(tt,j)==0)
{
opt(dp[u][i][(tt|(1<<i))|(1<<j)],dp[u][i-1][tt]+max(w2[i][j],g[i]+g[j]));
// if(u==1 && i==1 && j==0 && tt==0) cerr<<dp[u][1][3]<<'\n';
}
}
}
// if(u==1) cerr<<dp[u][1][3];
f[u]=dp[u][nchild[u]-1][(1<<nchild[u])-1];
}
int main()
{
// freopen("training.inp","r",stdin);
//freopen("training.out","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>m;
while(m--)
{
cin>>u>>v>>k;
edge tg={ u,v,k };
if(k==0) a[u].push_back(v),a[v].push_back(u);
else add.push_back(tg),sum+=k;
}
dfs(1);
for(i=0;i<add.size();i++)
{
edge x=add[i];
int u=x.u,v=x.v,k=x.k,p=LCA(u,v);
if(h[u]<h[v]) swap(u,v);
if((h[u]+h[v]-2*h[p])&1) continue;
edge tg={ u,v,k };
// cerr<<u<<" "<<v<<" "<<k<<'\n';
c[p].push_back(tg);
}
DFS(1);
cout<<sum-f[1];
}
Compilation message
training.cpp: In function 'void dfs(int)':
training.cpp:21:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | for(int i=0;i<a[u].size();i++)
| ~^~~~~~~~~~~~
training.cpp: In function 'void DFS(int)':
training.cpp:54:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for(int i=0;i<a[u].size();i++)
| ~^~~~~~~~~~~~
training.cpp:67:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for(int i=0;i<c[u].size();i++)
| ~^~~~~~~~~~~~
training.cpp:71:12: warning: unused variable 'sum' [-Wunused-variable]
71 | ll sum,sum1,sum2;
| ^~~
training.cpp: In function 'int main()':
training.cpp:117:19: warning: narrowing conversion of 'u' from 'long long int' to 'int' [-Wnarrowing]
117 | edge tg={ u,v,k };
| ^
training.cpp:117:21: warning: narrowing conversion of 'v' from 'long long int' to 'int' [-Wnarrowing]
117 | edge tg={ u,v,k };
| ^
training.cpp:117:23: warning: narrowing conversion of 'k' from 'long long int' to 'int' [-Wnarrowing]
117 | edge tg={ u,v,k };
| ^
training.cpp:122:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | for(i=0;i<add.size();i++)
| ~^~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
6488 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
10588 KB |
Output is correct |
| 2 |
Correct |
1 ms |
10588 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
13 ms |
96860 KB |
Output is correct |
| 2 |
Correct |
14 ms |
97368 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 2 |
Correct |
1 ms |
8540 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
14684 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12636 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
33112 KB |
Output is correct |
| 2 |
Correct |
5 ms |
33116 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
53852 KB |
Output is correct |
| 2 |
Correct |
6 ms |
51804 KB |
Output is correct |
| 3 |
Correct |
6 ms |
53816 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
12 ms |
97116 KB |
Output is correct |
| 2 |
Correct |
11 ms |
95320 KB |
Output is correct |
| 3 |
Correct |
11 ms |
95048 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
47876 KB |
Output is correct |
| 2 |
Correct |
8 ms |
53772 KB |
Output is correct |
| 3 |
Correct |
19 ms |
97148 KB |
Output is correct |
| 4 |
Correct |
8 ms |
54104 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
14 ms |
97116 KB |
Output is correct |
| 2 |
Correct |
19 ms |
97116 KB |
Output is correct |
| 3 |
Correct |
14 ms |
97116 KB |
Output is correct |
| 4 |
Correct |
13 ms |
95068 KB |
Output is correct |
