#include <bits/stdc++.h>
using namespace std;
#define int long long
struct Guy {
int a;
int b;
int cost;
};
const int N = 1000 + 7;
const int INF = (int) 1e18;
const int B = 10;
vector<Guy> offers[N];
int sz[N];
int dp[N][1 << B];
int n;
int m;
vector<int> g[N];
int totalG;
int dep[N];
int parrent[N];
int getLca(int a, int b) {
while (a != b) {
assert(a >= 1);
assert(b >= 1);
if (dep[a] > dep[b]) {
a = parrent[a];
} else {
b = parrent[b];
}
}
return a;
}
void build(int a, int p = -1) {
vector<int> relege;
parrent[a] = p;
for (auto &b : g[a]) {
if (b == p) {
continue;
}
dep[b] = 1 + dep[a];
relege.push_back(b);
build(b, a);
}
g[a] = relege;
}
int who[N];
int skip[N];
void dfs(int a) {
for (auto &b : g[a]) {
dfs(b);
}
for (auto &it : offers[a]) {
vector<int> pathX, pathY;
int C = it.cost;
{
int X = it.a, Y = it.b;
while (X != a) {
assert(X >= 1);
pathX.push_back(X);
X = parrent[X];
}
while (Y != a) {
assert(Y >= 1);
pathY.push_back(Y);
Y = parrent[Y];
}
reverse(pathX.begin(), pathX.end());
reverse(pathY.begin(), pathY.end());
}
{
skip[a] = 0;
for (auto &it : pathX) skip[it] = 0;
for (auto &it : pathY) skip[it] = 0;
}
if (!pathX.empty()) skip[a] += (1 << who[pathX[0]]);
if (!pathY.empty()) skip[a] += (1 << who[pathY[0]]);
for (int j = 0; j + 1 < (int) pathX.size(); j++) skip[pathX[j]] += (1 << who[pathX[j + 1]]);
for (int j = 0; j + 1 < (int) pathY.size(); j++) skip[pathY[j]] += (1 << who[pathY[j + 1]]);
int current = C;
for (auto &it : pathX) current += dp[it][(1 << sz[it]) - 1 - skip[it]];
for (auto &it : pathY) current += dp[it][(1 << sz[it]) - 1 - skip[it]];
dp[a][skip[a]] = max(dp[a][skip[a]], current);
}
for (int mask = 0; mask < (1 << sz[a]); mask++) {
for (int sub = mask; sub; sub = (sub - 1) & mask) {
dp[a][mask] = max(dp[a][mask], dp[a][sub] + dp[a][mask ^ sub]);
}
int mx = 0;
for (int it = 0; it < sz[a]; it++) {
if (mask & (1 << it)) {
mx += dp[g[a][it]][(1 << sz[g[a][it]]) - 1];
}
}
dp[a][mask] = max(dp[a][mask], mx);
}
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
/// freopen ("input", "r", stdin);
cin >> n >> m;
vector<Guy> guys;
for (int i = 1; i <= m; i++) {
int a, b, c;
cin >> a >> b >> c;
if (!c) {
totalG++;
g[a].push_back(b);
g[b].push_back(a);
} else {
guys.push_back({a, b, c});
}
}
assert(totalG == n - 1);
build(1);
for (int i = 1; i <= n; i++) {
sz[i] = (int) g[i].size();
for (int j = 0; j < (int) g[i].size(); j++) {
who[g[i][j]] = j;
}
}
int needToPay = 0, totalSm = 0;
for (auto &it : guys) {
int a = it.a;
int b = it.b;
int cost = it.cost;
if (dep[a] % 2 != dep[b] % 2) {
needToPay += cost;
} else {
int lca = getLca(a, b);
offers[lca].push_back(it);
totalSm += cost;
}
}
dfs(1);
cout << needToPay + (totalSm - dp[1][(1 << sz[1]) - 1]) << "\n";
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
480 KB |
Output is correct |
2 |
Correct |
1 ms |
588 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
4688 KB |
Output is correct |
2 |
Correct |
12 ms |
4728 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
1 ms |
460 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
752 KB |
Output is correct |
2 |
Correct |
1 ms |
756 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1612 KB |
Output is correct |
2 |
Correct |
1 ms |
1612 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
2564 KB |
Output is correct |
2 |
Correct |
3 ms |
2508 KB |
Output is correct |
3 |
Correct |
4 ms |
2508 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
4676 KB |
Output is correct |
2 |
Correct |
13 ms |
4812 KB |
Output is correct |
3 |
Correct |
5 ms |
4732 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
2668 KB |
Output is correct |
2 |
Correct |
5 ms |
2556 KB |
Output is correct |
3 |
Correct |
24 ms |
4772 KB |
Output is correct |
4 |
Correct |
6 ms |
2620 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
4736 KB |
Output is correct |
2 |
Correct |
27 ms |
4816 KB |
Output is correct |
3 |
Correct |
14 ms |
4844 KB |
Output is correct |
4 |
Correct |
7 ms |
4812 KB |
Output is correct |