This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using namespace chrono;
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
#define REP(i, n) for (int i = 0, _n = n; i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define FORE(it, s) for (__typeof(s.begin()) it = (s).begin(); it != (s).end(); ++it)
template <typename U, typename V> bool maximize(U &A, const V &B) { return (A < B) ? (A = B, true) : false; }
template <typename U, typename V> bool minimize(U &A, const V &B) { return (A > B) ? (A = B, true) : false; }
const int MAXN = 1e3 + 5;
int N, M, time_out[MAXN], deg[MAXN], high[MAXN], dp[MAXN][MASK(10)];
vector <int> adj[MAXN];
pair <int, int> par[MAXN];
struct Edge {
int u, v, w, LCA;
Edge(int u = 0, int v = 0, int w = 0) : u(u), v(v), w(w) {}
bool operator < (const Edge &oth) { return time_out[LCA] < time_out[oth.LCA]; }
};
void dfs(int u, int p) {
static int run = 0;
run++;
for (auto v : adj[u]) if(v != p) {
par[v] = make_pair(u, MASK(deg[u]++));
high[v] = high[u] + 1;
dfs(v, u);
}
time_out[u] = ++run;
}
int lca(int u, int v) {
if(high[u] < high[v]) swap(u, v);
while(high[u] > high[v]) u = par[u].first;
while(u != v) u = par[u].first, v = par[v].first;
return u;
}
void process(void) {
cin >> N >> M;
vector <Edge> edges(M);
int total_weights = 0;
for (auto &[u, v, w, _] : edges) {
cin >> u >> v >> w;
if(!w) {
adj[u].push_back(v);
adj[v].push_back(u);
} else total_weights += w;
}
dfs(1, 0);
for (auto &[u, v, _, LCA] : edges) {
LCA = lca(u, v);
}
sort(ALL(edges));
for (auto [u, v, w, LCA] : edges) {
if(w && high[u] % 2 != high[v] % 2) continue;
pair <int, int> A, B;
int cur = w;
for (A = make_pair(u, 0); A.first != LCA; A = par[A.first])
cur += dp[A.first][(MASK(deg[A.first]) - 1) ^ A.second];
for (B = make_pair(v, 0); B.first != LCA; B = par[B.first])
cur += dp[B.first][(MASK(deg[B.first]) - 1) ^ B.second];
REP(mask, MASK(deg[LCA])) if(!(mask & A.second) && !(mask & B.second)) {
maximize(dp[LCA][mask | A.second | B.second], dp[LCA][mask] + cur);
}
}
cout << total_weights - dp[1][MASK(deg[1]) - 1];
}
signed main() {
#define TASK "TASK"
if(fopen(TASK".inp", "r")) {
freopen(TASK".inp", "r", stdin);
freopen(TASK".out", "w", stdout);
}
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
auto start_time = steady_clock::now();
int test = 1;
// cin >> test;
for (int i = 1; i <= test; ++i) {
process();
// cout << '\n';
}
auto end_time = steady_clock::now();
cerr << "\nExecution time : " << duration_cast<milliseconds> (end_time - start_time).count() << "[ms]" << endl;
return (0 ^ 0);
}
Compilation message (stderr)
training.cpp: In function 'int main()':
training.cpp:82:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
82 | freopen(TASK".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
training.cpp:83:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
83 | freopen(TASK".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |