#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;
using pii = pair<int, int>;
const int K=10, N=1<<K;
vector<int> E[N], lca[N];
int id[N], d[N], par[N], pre[N], post[N];
int wsk;
int opt[N][K][K];//?
int dp[N][1<<K];//used subtrees
int dp2[N][5*N];//vert, out edg
int n, m;
vector<pair<int, pii > > edg, edg2;
vector<int> dob;
void dfs(int v, int p){
pre[v]=wsk++;
par[v]=p;
d[v]=d[p]+1;
for(int i=0; i<E[v].size(); i++)if(E[v][i]==p)swap(E[v][i], E[v].back());
if(p!=0)E[v].pop_back();
for(int i=0; i<E[v].size(); i++){
id[E[v][i]]=i;
dfs(E[v][i], v);
}
post[v]=wsk;
}
void dfs2(int v){
for(int u:E[v]){
dfs2(u);
dp[v][1<<id[u]]=dp2[u][0];
}
for(int e:lca[v]){
int u=edg[e].nd.st, w=edg[e].nd.nd;
while(par[w]!=v)w=par[w];
if(u==v){
dp[v][1<<id[w]]=max(edg[e].st + dp2[w][e], dp[v][1<<id[w]]);
}
else{
while(par[u]!=v)u=par[u];
if(v==1 && e==7){
//cout<<id[u]<<" "<<id[w]<<"\n";
//cout<<dp2[u][e]<<" "<<dp2[w][e]<<"\n";
//cout<<edg2[7].nd.st<<" "<<edg2[7].nd.nd<<"\n";
}
dp[v][(1<<id[u])+(1<<id[w])]=max(edg[e].st+dp2[u][e]+dp2[w][e], dp[v][(1<<id[u])+(1<<id[w])]);
}
}
for(int i=0; i<(1<<E[v].size()); i++){
for(int j=i; ; j=(j-1)&i){
dp[v][i]=max(dp[v][i], dp[v][j]+dp[v][i-j]);
if(j==0)break;
}
}
for(int e:dob){
if(edg[e].nd.st==v && pre[edg[e].nd.nd]>=post[v]){
dp2[v][e]=dp[v][(1<<E[v].size())-1];
}
if(edg[e].nd.nd==v){
dp2[v][e]=dp[v][(1<<E[v].size())-1];
}
if(par[edg2[e].nd.st]==v ^ par[edg2[e].nd.nd]==v){
if(par[edg2[e].nd.st]==v){
if(v==2 && e==7){
//cout<<dp2[edg2[e].nd.st][e]<<" "<<dp[v][(1<<E[v].size())-1-(1<<id[edg2[e].nd.st])]<<" ";
}
dp2[v][e]=dp[v][(1<<E[v].size())-1-(1<<id[edg2[e].nd.st])]+dp2[edg2[e].nd.st][e];
if(v==2 && e==7){
//cout<<dp2[v][e];
}
edg2[e].nd.st=v;
}
if(par[edg2[e].nd.nd]==v){
dp2[v][e]=dp[v][(1<<E[v].size())-1-(1<<id[edg2[e].nd.nd])]+dp2[edg[e].nd.nd][e];
edg2[e].nd.nd=v;
}
}
}
dp2[v][0]=dp[v][(1<<E[v].size())-1];
}
int main(){
cin>>n>>m;
int sum=0;
for(int i=0; i<m; i++){
int u, v, w;
cin>>u>>v>>w;
sum+=w;
edg.push_back({w, {u, v}});
if(w==0){
E[u].push_back(v);
E[v].push_back(u);
}
}
dfs(1, 0);
sort(edg.begin(), edg.end());
for(int i=n-1; i<m; i++){
if(pre[edg[i].nd.st]>pre[edg[i].nd.nd])swap(edg[i].nd.st, edg[i].nd.nd);
int u=edg[i].nd.st, v=edg[i].nd.nd;
if((d[u]&1)!=(d[v]&1)){
continue;
}
if(d[u]<d[v])swap(u, v);
while(d[u]>d[v]){
u=par[u];
}
while(u!=v){
u=par[u];
v=par[v];
}
dob.push_back(i);
lca[u].push_back(i);
}
edg2=edg;
dfs2(1);
/*for(int i=1; i<=n; i++){
cout<<i<<" "<<E[i].size()<<"\n";
for(int j=0; j<(1<<E[i].size()); j++)cout<<dp[i][j]<<" ";
cout<<"\n";
for(int j=0; j<edg.size(); j++)cout<<dp2[i][j]<<" ";
cout<<"\n";
}*/
cout<<sum-dp2[1][0];
}
Compilation message
training.cpp: In function 'void dfs(int, int)':
training.cpp:20:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | for(int i=0; i<E[v].size(); i++)if(E[v][i]==p)swap(E[v][i], E[v].back());
| ~^~~~~~~~~~~~
training.cpp:22:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | for(int i=0; i<E[v].size(); i++){
| ~^~~~~~~~~~~~
training.cpp: In function 'void dfs2(int)':
training.cpp:62:24: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
62 | if(par[edg2[e].nd.st]==v ^ par[edg2[e].nd.nd]==v){
| ~~~~~~~~~~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
0 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
764 KB |
Output is correct |
| 2 |
Correct |
1 ms |
724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
20564 KB |
Output is correct |
| 2 |
Correct |
19 ms |
20652 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
468 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
3668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
8404 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
21840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
7380 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
8436 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
15700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
