#include <bits/stdc++.h>
#define x first.first
#define y first.second
#define cost second
#define ub(x) (x&(-x))
using namespace std;
typedef pair <pair <int, int>, int> PIII;
constexpr int NMAX = 1005;
int N, M;
vector <int> G[NMAX];
vector <PIII> Edges;
vector <int> E[NMAX];
int Dad[NMAX];
int ans;
void Read () {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> M;
for (int i = 1; i <= M; ++ i ) {
PIII e;
cin >> e.x >> e.y >> e.cost;
if (e.cost == 0) {
G[e.x].push_back(e.y);
G[e.y].push_back(e.x);
}
else {
Edges.push_back(e);
}
}
}
bool viz[NMAX];
void Reset () {
for (int i = 1; i <= N; ++ i )
viz[i] = false;
}
bool CheckOdd (int start, int finish) {
queue <pair <int, bool> > Q;
Q.push({start, 0});
viz[start] = true;
while (!Q.empty()) {
int nod = Q.front().first;
bool good = Q.front().second;
good = !good;
Q.pop();
for (auto it : G[nod]) {
if (viz[it]) continue;
viz[it] = true;
Q.push({it, good});
if (it == finish) return good;
}
}
assert(false);
}
void Do_Direct_Graph (int Node, int dad = -1) {
vector <int> aux;
Dad[Node] = dad;
for (auto it : G[Node]) {
if (it == dad) continue;
Do_Direct_Graph(it, Node);
aux.push_back(it);
}
G[Node].clear();
G[Node] = aux;
}
int FindLca (int a, int b) {
Reset();
while (a != -1) {
viz[a] = 1;
a = Dad[a];
}
while (!viz[b]) b = Dad[b];
return b;
}
int who[2048];
void Precompute () {
for (int i = 2; i < 2048; ++ i )
who[i] = who[i/2] + 1;
vector <PIII> aux;
for (auto it : Edges) {
ans += it.cost;
Reset();
if (!CheckOdd(it.x, it.y))
aux.push_back(it);
}
Edges = aux;
Do_Direct_Graph(1);
for (int i = 0; i < Edges.size(); ++ i )
E[FindLca(Edges[i].x, Edges[i].y)].push_back(i);
}
int dp[NMAX][2048];
int sum_of_mask[2048];
int ToNode[NMAX];
int anc[NMAX];
void ComputeToNode (int Node, int value, int commonAncestor) {
anc[Node] = commonAncestor;
ToNode[Node] = value + dp[Node][(1<<G[Node].size())-1];
int mask = (1<<G[Node].size()) - 1;
for (int i = 0; i < G[Node].size(); ++ i )
ComputeToNode(G[Node][i], value + dp[Node][mask^(1<<i)], (commonAncestor == -1 ? i : commonAncestor));
}
void Solve (int Node) {
for (int i = 0; i < G[Node].size(); ++ i )
Solve(G[Node][i]);
ComputeToNode(Node, 0, -1);
for (int mask = 1; mask < (1<<G[Node].size()); ++ mask ) {
int last_son_ind = who[ub(mask)];
sum_of_mask[mask] = sum_of_mask[mask-ub(mask)] + dp[G[Node][last_son_ind]][(1<<G[G[Node][last_son_ind]].size())-1];
dp[Node][mask] = sum_of_mask[mask];
for (auto it : E[Node]) {
int a = Edges[it].x;
int b = Edges[it].y;
int c = Edges[it].cost;
if (b == Node) swap(a, b);
if (a == Node) {
if (!(mask&(1<<anc[b]))) continue;
dp[Node][mask] = max(dp[Node][mask], dp[Node][(mask^(1<<anc[b]))] + c + ToNode[b]);
}
else {
if (!(mask&(1<<anc[a])) || (!(mask&(1<<anc[b])))) continue;
int state = (mask^(1<<anc[a])^(1<<anc[b]));
dp[Node][mask] = max(dp[Node][mask], dp[Node][state] + c + ToNode[a] + ToNode[b]);
}
}
}
}
int main () {
Read();
Precompute();
Solve(1);
cout << ans - dp[1][(1<<(G[1].size()))-1] << '\n';
return 0;
}
Compilation message
training.cpp: In function 'void Precompute()':
training.cpp:117:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
117 | for (int i = 0; i < Edges.size(); ++ i )
| ~~^~~~~~~~~~~~~~
training.cpp: In function 'void ComputeToNode(int, int, int)':
training.cpp:132:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
132 | for (int i = 0; i < G[Node].size(); ++ i )
| ~~^~~~~~~~~~~~~~~~
training.cpp: In function 'void Solve(int)':
training.cpp:137:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
137 | for (int i = 0; i < G[Node].size(); ++ i )
| ~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
596 KB |
Output is correct |
| 2 |
Correct |
1 ms |
596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
4580 KB |
Output is correct |
| 2 |
Correct |
36 ms |
4584 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| # |
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 |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
724 KB |
Output is correct |
| 2 |
Correct |
4 ms |
636 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
980 KB |
Output is correct |
| 2 |
Correct |
7 ms |
852 KB |
Output is correct |
| 3 |
Correct |
14 ms |
1492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
2124 KB |
Output is correct |
| 2 |
Correct |
24 ms |
1132 KB |
Output is correct |
| 3 |
Correct |
14 ms |
1456 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
724 KB |
Output is correct |
| 2 |
Correct |
11 ms |
1660 KB |
Output is correct |
| 3 |
Correct |
48 ms |
4444 KB |
Output is correct |
| 4 |
Correct |
13 ms |
1764 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
47 ms |
1964 KB |
Output is correct |
| 2 |
Correct |
68 ms |
4500 KB |
Output is correct |
| 3 |
Correct |
52 ms |
1548 KB |
Output is correct |
| 4 |
Correct |
22 ms |
1340 KB |
Output is correct |
