#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],w[11],w2[11][11],dp[11][1024];
void dfs(int u)
{
for(int v:a[u])
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)
{
u=p[u];
ll res=0;
while(u!=v) res+=g[u]-f[u],u=p[u];
return res;
}
void DFS(int u)
{
int nchild=0,i,j,tt;
for(int v:a[u])
if(v!=p[u])
{
DFS(v);
g[u]+=f[v];
}
for(int v:a[u])
if(v!=p[u]) num[v]=nchild++;
memset(w,0,sizeof(w));
memset(w2,0,sizeof(w2));
memset(dp,0,sizeof(dp));
for(edge x:c[u])
{
int v1=x.u,v2=x.v,k=x.k,tg1,tg2;
ll sum,sum1,sum2;
if(v2==u)
{
tg1=num[nearest(v1,u)];
opt(w[tg1],climb(v1,u)+k);
}
else
{
tg1=num[nearest(v1,u)]; sum1=climb(v1,u);
tg2=num[nearest(v2,u)]; sum2=climb(v2,u);
opt(w2[tg1][tg2],sum1+sum2+k);
opt(w2[tg2][tg1],sum1+sum2+k);
}
}
if(nchild==0) return ;
dp[0][0]=0;
dp[0][1]=w[0];
for(i=1;i<nchild;i++)
{
for(tt=0;tt<(1<<i)-1;tt++)
{
opt(dp[i][tt],dp[i-1][tt]);
opt(dp[i][tt|(1<<i)],dp[i-1][tt]+w[i]);
for(j=0;j<i;j++)
if(BIT(tt,j)==0)
opt(dp[i][(tt|(1<<i))|(1<<j)],dp[i-1][tt]+w2[i][j]);
}
}
ll ma=0;
for(tt=0;tt<(1<<nchild);tt++) ma=max(ma,dp[nchild-1][tt]);
f[u]=g[u]+ma;
}
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;
if(k==0) a[u].push_back(v),a[v].push_back(u);
else add.push_back({ u,v,k }),sum+=k;
}
dfs(1);
for(edge x:add)
{
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;
c[p].push_back({ u,v,k });
}
DFS(1);
cout<<sum-f[1];
}
Compilation message
training.cpp: In function 'void DFS(int)':
training.cpp:61:12: warning: unused variable 'sum' [-Wunused-variable]
61 | ll sum,sum1,sum2;
| ^~~
training.cpp: In function 'int main()':
training.cpp:106:30: warning: narrowing conversion of 'u' from 'long long int' to 'int' [-Wnarrowing]
106 | else add.push_back({ u,v,k }),sum+=k;
| ^
training.cpp:106:32: warning: narrowing conversion of 'v' from 'long long int' to 'int' [-Wnarrowing]
106 | else add.push_back({ u,v,k }),sum+=k;
| ^
training.cpp:106:34: warning: narrowing conversion of 'k' from 'long long int' to 'int' [-Wnarrowing]
106 | else add.push_back({ u,v,k }),sum+=k;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
600 KB |
Output is correct |
| 2 |
Correct |
5 ms |
860 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
604 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
