#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,jm,pi,dep[1009],msh[1009][14],lf[1009],rg[1009],tim,lc,dp[1009],dp2[1009][1009],dpk[1009][2109],nmb[1009];
pair <pair <int, int>, int> p[5009];
vector <pair <pair <int, int>, pair <int, int> > > vv[1009];
vector <int> vvl[1009],vvvl[1009];
vector <pair <int, int> > vvv[1009];
vector <int> v[1009];
void dfs(int q, int w){
dep[q]=dep[w]+1;
msh[q][0]=w;
for(int h=1; h<=12; h++) msh[q][h]=msh[msh[q][h-1]][h-1];
tim++;
lf[q]=rg[q]=tim;
for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
if((*it)==w) continue;
dfs((*it),q);
if(rg[q]<rg[(*it)]) rg[q]=rg[(*it)];
}
}
bool anc(int q, int w){
if(lf[q]<=lf[w]&&rg[q]>=rg[w]) return 1; else return 0;
}
int lca(int q, int w){
if(anc(q,w)) return q;
if(anc(w,q)) return w;
for(int h=12; h>=0; h--){
if(msh[q][h]!=0&&anc(msh[q][h],w)==0) q=msh[q][h];
}
return msh[q][0];
}
int lca2(int q, int w){
for(int h=12; h>=0; h--){
if(msh[q][h]!=0&&anc(msh[q][h],w)==0) q=msh[q][h];
}
return q;
}
void dfs2(int q, int w){
if(v[q].size()==1&&w!=0){
return;
}
dp[q]=0;
int zu=0;
for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
if((*it)==w) continue;
zu++;
nmb[(*it)]=zu-1;
dfs2((*it),q);
dp[q]+=dp[(*it)];
}
dpk[q][0]=dp[q];
int sh=v[q].size();
if(q!=1) sh--;
for(int h=1; h<(1<<sh); h++){
int hh=0;
for(hh=0; hh<sh; hh++){
if((h&(1<<hh))!=0){
if(dpk[q][h]<dpk[q][(h^(1<<hh))]) dpk[q][h]=dpk[q][(h^(1<<hh))];
}
}
hh=-1;
for(vector <pair <int, int> >::iterator it=vvv[q].begin(); it!=vvv[q].end(); it++){
hh++;
if((h&(1<<nmb[(*it).second]))==0) continue;
zx=dpk[q][(h^(1<<nmb[(*it).second]))]+max(0,dp2[(*it).second][(*it).first]-dp[(*it).second]+vvvl[q][hh]);
/*if(q==1){
cout<<vvvl[q].size()<<endl;
cout<<(*it).first<<" ka "<<(*it).second<<" "<<zx<<" "<<vvvl[q][hh]<<endl;
}*/
if(dpk[q][h]<zx) dpk[q][h]=zx;
}
hh=-1;
for(vector <pair <pair <int, int>, pair <int, int> > >::iterator it=vv[q].begin(); it!=vv[q].end(); it++){
hh++;
if((h&(1<<nmb[(*it).first.second]))==0||(h&(1<<nmb[(*it).second.second]))==0) continue;
zx=dpk[q][(h^((1<<nmb[(*it).first.second])|(1<<nmb[(*it).second.second])))]+max(0,dp2[(*it).first.second][(*it).first.first]-dp[(*it).first.second]+dp2[(*it).second.second][(*it).second.first]-dp[(*it).second.second]+vvl[q][hh]);
if(dpk[q][h]<zx) dpk[q][h]=zx;
}
}
zx=(1<<sh)-1;
if(dp[q]<dpk[q][zx]) dp[q]=dpk[q][zx];
dp2[q][q]=dp[q];
for(i=1; i<=a; i++){
if(anc(q,i)==0||q==i) continue;
xc=lca2(i,q);
dp2[q][i]=dp2[xc][i]+dpk[q][(zx^(1<<nmb[xc]))]-dp[xc];
}
//cout<<q<<" "<<dp[q]<<endl;
}
int main(){
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>a>>b;
for(i=1; i<=b; i++){
cin>>c>>d>>e;
jm+=e;
if(e==0){
v[c].push_back(d);
v[d].push_back(c);
}else{
pi++;
p[pi].first.first=c;
p[pi].first.second=d;
p[pi].second=e;
}
}
dfs(1,0);
for(i=1; i<=pi; i++){
c=p[i].first.first;d=p[i].first.second;e=p[i].second;
lc=lca(c,d);
if((dep[c]+dep[d]-dep[lc]*2)%2==1) continue;
if(anc(c,d)){
vvv[c].push_back(make_pair(d,lca2(d,c)));
vvvl[c].push_back(e);
continue;
}
if(anc(d,c)){
vvv[d].push_back(make_pair(c,lca2(c,d)));
vvvl[d].push_back(e);
continue;
}
vv[lc].push_back(make_pair(make_pair(c,lca2(c,d)),make_pair(d,lca2(d,c))));
vvl[lc].push_back(e);
}
dfs2(1,0);
/*cout<<dp2[2][3]<<" "<<dp[2];
cout<<endl<<endl;*/
cout<<jm-dp[1];
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
640 KB |
Output is correct |
| 2 |
Correct |
1 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
896 KB |
Output is correct |
| 2 |
Correct |
1 ms |
896 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
8696 KB |
Output is correct |
| 2 |
Correct |
61 ms |
8696 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
512 KB |
Output is correct |
| 2 |
Correct |
1 ms |
640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
640 KB |
Output is correct |
| 2 |
Correct |
1 ms |
768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
896 KB |
Output is correct |
| 2 |
Correct |
1 ms |
896 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1408 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1152 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1792 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1536 KB |
Output is correct |
| 3 |
Correct |
9 ms |
2944 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
4608 KB |
Output is correct |
| 2 |
Correct |
13 ms |
2176 KB |
Output is correct |
| 3 |
Correct |
8 ms |
3072 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
1280 KB |
Output is correct |
| 2 |
Correct |
6 ms |
3072 KB |
Output is correct |
| 3 |
Correct |
23 ms |
8576 KB |
Output is correct |
| 4 |
Correct |
7 ms |
3328 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
4608 KB |
Output is correct |
| 2 |
Correct |
48 ms |
8724 KB |
Output is correct |
| 3 |
Correct |
16 ms |
3584 KB |
Output is correct |
| 4 |
Correct |
13 ms |
3024 KB |
Output is correct |
