#include <bits/stdc++.h>
#define DIM 1010
using namespace std;
vector <int> L[DIM];
long long dp[DIM][1050],best[DIM];
struct muchie{
int x,y,cost;
};
vector <muchie> mch,v[DIM];
int level[DIM],fth[DIM],first[DIM],E[DIM*3],p[DIM*3];
pair <int,int> rmq[20][DIM*3];
int n,m,i,j,x,y,cost,k;
void dfs (int nod, int tata){
fth[nod] = tata;
level[nod] = 1 + level[tata];
E[++k] = nod;
first[nod] = k;
for (auto vecin : L[nod])
if (vecin != tata){
dfs (vecin,nod);
E[++k] = nod;
}
}
int get_lca (int x, int y){
int posx = first[x], posy = first[y];
if (posx > posy)
swap (posx,posy);
int nr = p[posy-posx+1];
pair <int,int> sol = min (rmq[nr][posx],rmq[nr][posy-(1<<nr)+1]);
return E[sol.second];
}
int get_poz (int x, int y){
for (int i=0;i<L[x].size();i++)
if (L[x][i] == y)
return i;
}
void dfs2 (int nod, int tata){
int ok = 0;
for (auto vecin : L[nod]){
ok = 1;
dfs2 (vecin,nod);
}
if (!ok){
best[nod] = 0;
} else {
int sz = L[nod].size();
int maxi = (1<<sz);
for (int mask=0;mask<maxi;mask++)
for (int bit=0;bit<sz;bit++){
int vecin = L[nod][bit];
if (mask & (1<<bit))
dp[nod][mask] += best[vecin];
}
for (auto it : v[nod]){ /// nod e lca
int x = it.x, y = it.y, cost = it.cost;
if (x != nod && y != nod){
long long sum = best[x] + best[y] + cost;
int val = x;
while (fth[val] != nod){
//int poz = get_poz (fth[val],val);
//sum += dp[fth[val]][( (1<<L[fth[val]].size()) - 1 ) ^ (1<<poz)];
for (auto it : L[fth[val]]){
if (it != val)
sum += best[it];
}
val = fth[val];
}
int pozx = get_poz (nod,val);
val = y;
while (fth[val] != nod){
for (auto it : L[fth[val]]){
if (it != val)
sum += best[it];
}
val = fth[val];
}
int pozy = get_poz (nod,val);
sum += dp[nod][((1<<L[nod].size()) - 1) ^ (1<<pozx) ^ (1<<pozy) ];
for (int mask=maxi-1;mask>=0;mask--){
if ( !((mask & (1<<pozx)) && (mask & (1<<pozy)) ))
continue;
dp[nod][mask] = max (dp[nod][mask],dp[nod][mask^(1<<pozx)^(1<<pozy)] + sum);
}
} else { /// am un singur lant
int val = (x != nod) ? (x) : (y);
long long sum = best[val] + cost;
while (fth[val] != nod){
for (auto it : L[fth[val]]){
if (it != val)
sum += best[it];
}
val = fth[val];
}
int poz = get_poz (nod,val);
sum += dp[nod][((1<<L[nod].size()) - 1) ^ (1<<poz)];
for (int mask=maxi-1;mask>=0;mask--){
if (!(mask & (1<<poz)))
continue;
dp[nod][mask] = max (dp[nod][mask], dp[nod][mask^(1<<poz)] + sum);
}
}
}
for (int mask=0;mask<maxi;mask++)
best[nod] = max (best[nod],dp[nod][mask]);
}
}
int main (){
//ifstream cin ("date.in");
//ofstream cout ("date.out");
cin>>n>>m;
for (i=1;i<=m;i++){
cin>>x>>y>>cost;
if (!cost){
L[x].push_back(y);
L[y].push_back(x);
} else mch.push_back({x,y,cost});
}
dfs (1,0);
for (i=2;i<=n;i++){
for (j=0;j<L[i].size();j++)
if (L[i][j] == fth[i])
break;
swap (L[i][j],L[i].back());
L[i].pop_back();
}
for (i=1;i<=k;i++)
rmq[0][i] = make_pair(level[E[i]],i);
for (i=1;(1<<i)<=k;i++)
for (j=1;j<=k;j++){
rmq[i][j] = rmq[i-1][j];
if (j + (1<<(i-1)) <= k && rmq[i-1][j + (1<<i-1)].first < rmq[i][j].first)
rmq[i][j] = rmq[i-1][j + (1<<i-1)];
}
for (i=2;i<=k;i++)
p[i] = p[i/2] + 1;
long long total = 0;
for (auto it : mch){
int x = it.x, y = it.y;
if (level[x] > level[y])
swap (x,y);
total += it.cost;
if ( (level[y] - level[x]) % 2 )
continue;
int lca = get_lca (x,y);
v[lca].push_back({x,y,it.cost});
}
dfs2 (1,0);
cout<<total - best[1];
return 0;
}
Compilation message
training.cpp: In function 'int get_poz(int, int)':
training.cpp:43:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for (int i=0;i<L[x].size();i++)
| ~^~~~~~~~~~~~
training.cpp: In function 'int main()':
training.cpp:164:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
164 | for (j=0;j<L[i].size();j++)
| ~^~~~~~~~~~~~
training.cpp:177:58: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
177 | if (j + (1<<(i-1)) <= k && rmq[i-1][j + (1<<i-1)].first < rmq[i][j].first)
| ~^~
training.cpp:178:47: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
178 | rmq[i][j] = rmq[i-1][j + (1<<i-1)];
| ~^~
training.cpp: In function 'int get_poz(int, int)':
training.cpp:46:1: warning: control reaches end of non-void function [-Wreturn-type]
46 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
0 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
4748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
2380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
972 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
2380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
