#include<bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
#define ll long long
#define ld long double
#define ff first
#define ss second
#define db double
#define time_begin() auto begin = chrono::high_resolution_clock::now()
#define time_end() auto end = chrono::high_resolution_clock::now(); auto elapsed = chrono::duration_cast<chrono::nanoseconds>(end-begin); auto sec = elapsed.count() * 1e-9; cerr << "\n\nExecution time: " << sec << " seconds";
#define check_time() cerr << "\nStatus : "; if (sec>1) cerr << "Time Limit Exceeded 1!!!1!111"; else cerr << "You good brother"
#define precision(x) fixed << setprecision((x))
#define check_ok() cout << "it aight" << '\n'
using namespace std;
void setIO(string s = ""){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
if (!s.empty()){
freopen((s+".in").c_str(), "r", stdin);
freopen((s+".out").c_str(), "w", stdout);
}
}
const int D = 10;
const int N = 1000;
int up[N][D+1];
int order[N];
int deg[N];
int depth[N];
pair<int, int> par[N];
int cnt = 0;
vector<int> adj[N];
struct edge{
int u, v, c, lca;
edge(int uu, int vv, int cc, int l = -1) : u(uu), v(vv), c(cc), lca(l){
}
bool operator < (const edge& other){
return order[lca] < order[other.lca];
}
};
vector<edge> edges;
void dfs(int u = 0, int p = 0){
// cout << u << ' ' << p << '\n';
// check_ok();
up[u][0] = p;
for (int i = 1; i <= D; i++){
up[u][i] = up[up[u][i-1]][i-1];
}
for (int v : adj[u]){
if (v==p) continue;
depth[v] = depth[u]+1;
par[v] = {u, 1<<deg[u]};
deg[u]++;
dfs(v, u);
}
order[u] = ++cnt;
}
int jump(int u, int h){
// cout << "jumps ";
// check_ok();
for (int i = 0; i <= D; i++){
if (h & (1<<i)) u = up[u][i];
}
return u;
}
int LCA(int a, int b){
// cout << "lca ";
// check_ok();
if (depth[a] < depth[b]) swap(a, b);
int dif = depth[a] - depth[b];
a = jump(a, dif);
if (a==b) return a;
for (int i = D; i >= 0; i--){
if (up[a][i] != up[b][i]){
a = up[a][i];
b = up[b][i];
}
}
return up[a][0];
}
int dp[N][1<<D], mask1, mask2;
void build(){
//cout << "build ";
//check_ok();
for (const edge& e : edges){
if ((depth[e.u]+depth[e.v])&1 && e.c) continue;
int a = e.u, b = e.v, c = e.c, lca = e.lca;
// cout << a << ' ' << b << ' ' << lca << '\n';
for (mask1 = 0; a != lca;tie(a, mask1) = par[a]){
c += dp[a][mask1];
}
for (mask2 = 0; b != lca; tie(b, mask2) = par[b]) c += dp[b][mask2];
mask1 |= mask2;
for (int mask = (1<<deg[lca])-1; mask >= 0; mask--){
if (mask & mask1) continue;
dp[lca][mask] = max(dp[lca][mask], c + dp[lca][mask|mask1]);
}
}
}
int main(){
int n, m;
cin >> n >> m;
int sum = 0;
for (int i = 1; i <= m; i++){
int a, b, cost;
cin >> a >> b >> cost;
a--; b--;
if (!cost){
adj[a].push_back(b);
adj[b].push_back(a);
}
sum += cost;
edges.push_back(edge(a, b, cost));
}
memset(up, -1, sizeof up);
memset(deg, 0, sizeof deg);
depth[0] = 0;
dfs();
for (edge& e : edges){
if ((depth[e.u]+depth[e.v])&1 && e.c) continue;
e.lca = LCA(e.u, e.v);
// cout << e.u << ' ' << e.v << ' ' << e.lca << '\n';
}
sort(edges.begin(), edges.end());
build();
cout << sum - dp[0][0];
}
/*
5 8
2 1 0
3 2 0
4 3 0
5 4 0
1 3 2
3 5 2
2 4 5
2 5 1
*/
Compilation message
training.cpp: In function 'void setIO(std::string)':
training.cpp:25:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
25 | freopen((s+".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
training.cpp:26:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
26 | freopen((s+".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Correct |
0 ms |
604 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
4700 KB |
Output is correct |
| 2 |
Correct |
4 ms |
4700 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
604 KB |
Output is correct |
| 2 |
Correct |
0 ms |
604 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
860 KB |
Output is correct |
| 2 |
Correct |
1 ms |
860 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
1116 KB |
Output is correct |
| 2 |
Correct |
1 ms |
860 KB |
Output is correct |
| 3 |
Correct |
2 ms |
1504 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
2140 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1116 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1628 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
856 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1628 KB |
Output is correct |
| 3 |
Correct |
7 ms |
4700 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1884 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
2140 KB |
Output is correct |
| 2 |
Correct |
6 ms |
4700 KB |
Output is correct |
| 3 |
Correct |
4 ms |
1628 KB |
Output is correct |
| 4 |
Correct |
3 ms |
1368 KB |
Output is correct |
