#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 1600 + 5, mod = 1e9 + 7; // !
int t, in[N], out[N], timer, P[N][20], h[N], edge[N];
vector<int> V[N], v;
int dp[N][N];
vector<pair<pair<int,int>, int> > x[N];
void dfs0(int u, int p) {
in[u] = ++timer;
h[u] = h[p] + 1;
P[u][0] = p; v.push_back(u);
for(int i = 1; i <= 18; i++) P[u][i] = P[P[u][i - 1]][i - 1];
for(int i = 0; i < V[u].size(); i++) {
int v = V[u][i];
if(v != p) dfs0(v, u);
else {
swap(V[u][i], V[u].back());
--i;
V[u].pop_back();
}
}
out[u] = timer;
}
bool check(int u, int v) {
return (in[u] <= in[v] && out[v] <= out[u]);
}
int lca(int u, int v) {
if(check(u, v)) return u;
if(check(v, u)) return v;
for(int i = 18; i >= 0; i--) {
if(P[u][i] && !check(P[u][i], v)) u = P[u][i];
}
return P[u][0];
}
int all(int X) {
return dp[X][(1 << (int)V[X].size()) - 1];
}
int n, UP[N];
void dfs(int u) {
for(int i = 0; i < V[u].size(); i++) {
edge[V[u][i]] = i;
dfs(V[u][i]);
}
vector<int> dp_(n + 2);
for(int i = 0; i < v.size(); i++) {
if(v[i] == u) continue;
if(check(u, v[i])) {
int x = v[i];
dp_[x] = dp_[P[x][0]] - all(P[x][0]) + all(x) + dp[P[x][0]][(1 << V[x].size()) - 1 - (1 << edge[x])];
if(P[x][0] == u) UP[x] = x;
else UP[x] = UP[P[x][0]];
}
}
vector<int> mask(x[u].size()), ans(x[u].size());
for(int j = 0; j < x[u].size(); j++) {
ans[j] = x[u][j].s;
if(x[u][j].f.f != u) {
mask[j] |= 1 << edge[UP[x[u][j].f.f]];
ans[j] += dp_[x[u][j].f.f];
}
if(x[u][j].f.s != u){
mask[j] |= 1 << edge[UP[x[u][j].f.s]];
ans[j] += dp_[x[u][j].f.s];
}
}
for(int i = 0; i < (1 << (int)V[u].size()); i++) {
for(int j = 0; j < V[u].size(); j++) {
if((1 << j) & i) dp[u][i] = max(dp[u][i], dp[u][i - (1 << j)] + all(V[u][j]));
}
for(int j = 0; j < x[u].size(); j++) {
if((mask[j] & i) == mask[j]) dp[u][i] = max(dp[u][i], dp[u][i - mask[j]] + ans[j]);
}
}
// cout << u << " " << all(u) << endl;
}
main(){
int m;
cin >> n >> m;
vector<pair<pair<int,int>, int> > e;
while(m--) {
int u, v, c;
cin >> u >> v >> c;
if(!c) V[u].push_back(v), V[v].push_back(u);
else {
e.push_back({{u, v}, c});
}
// assert(V[u].size() <= 2); assert(V[v].size() <= 2);
}
int root = 1;
dfs0(root, 0);
int ans = 0, tot = 0;
for(int i = 0; i < e.size(); i++) {
int u = e[i].f.f, v = e[i].f.s, c = e[i].s;
if((h[u] + h[v] - 2 * h[lca(u, v)]) % 2) {
ans += c; continue;
}
tot += c;
x[lca(u, v)].push_back({{u, v}, c});
}
dfs(root);
cout << tot - all(root) + ans;
}
Compilation message
training.cpp: In function 'void dfs0(long long int, long long int)':
training.cpp:17:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | for(int i = 0; i < V[u].size(); i++) {
| ~~^~~~~~~~~~~~~
training.cpp: In function 'void dfs(long long int)':
training.cpp:45:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for(int i = 0; i < V[u].size(); i++) {
| ~~^~~~~~~~~~~~~
training.cpp:50:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for(int i = 0; i < v.size(); i++) {
| ~~^~~~~~~~~~
training.cpp:60:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for(int j = 0; j < x[u].size(); j++) {
| ~~^~~~~~~~~~~~~
training.cpp:72:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for(int j = 0; j < V[u].size(); j++) {
| ~~^~~~~~~~~~~~~
training.cpp:75:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for(int j = 0; j < x[u].size(); j++) {
| ~~^~~~~~~~~~~~~
training.cpp: At global scope:
training.cpp:81:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
81 | main(){
| ^~~~
training.cpp: In function 'int main()':
training.cpp:97:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for(int i = 0; i < e.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
596 KB |
Output is correct |
| 2 |
Correct |
1 ms |
520 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
4820 KB |
Output is correct |
| 2 |
Correct |
10 ms |
4948 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
1108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
2496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
1108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
2540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
