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;
const int N = 1005;
const int INF = 0x3f3f3f3f;
int n, m;
vector<int> adj[N], child[N], paths[N];
vector<array<int, 3>> edges, tmpe;
int dep[N], dp[N][1<<10], tin[N], tout[N], timer = -1, up[N][20];
int id[N], iid[10], lol[10][10];
int ans;
void dfs1(int v, int p){
tin[v] = ++timer;
up[v][0] = p;
for(int i = 1; i<20; i++) up[v][i] = up[up[v][i-1]][i-1];
for(auto u : adj[v]){
if(u == p) continue;
dep[u] = dep[v]+1;
child[v].push_back(u);
dfs1(u, v);
}
tout[v] = timer;
}
bool isPar(int u, int v){
return tin[u] <= tin[v] && tout[v] <= tout[u];
}
int LCA(int u, int v){
if(isPar(u, v)) return u;
if(isPar(v, u)) return v;
for(int i = 19; i>=0; i--)
if(!isPar(up[u][i], v)) u = up[u][i];
return up[u][0];
}
void dfs2(int v, int p){
for(auto u : adj[v]){
if(u == p) continue;
dfs2(u, v);
}
int cnt = 0;
for(auto u : child[v])
id[u] = cnt, iid[cnt++] = u;
memset(lol, -1, sizeof lol);
for(int i : paths[v]){
auto e = edges[i];
int a = e[0], b = e[1], w = e[2];
if(dep[a] > dep[b]) swap(a, b);
int ca = -1, cb = -1;
int res = w;
while(a != v){
if(ca == -1) res += dp[a][(1<<child[a].size())-1];
else res += dp[a][((1<<child[a].size())-1)^(1<<id[ca])];
ca = a, a = up[a][0];
}
while(b != v){
if(cb == -1) res += dp[b][(1<<child[b].size())-1];
else res += dp[b][((1<<child[b].size())-1)^(1<<id[cb])];
cb = b, b = up[b][0];
}
if(ca == -1) ca = cb;
ca = id[ca], cb = id[cb];
if(ca > cb) swap(ca, cb);
lol[ca][cb] = max(lol[ca][cb], res);
}
memset(dp[v], -1, sizeof(int)*(1<<cnt));
dp[v][0] = 0;
for(int mask = 0, end = (1<<cnt); mask<end; ++mask){
int tmp = 0;
for(int i = 0; i<cnt; i++){
if(!(mask&(1<<i))) continue;
tmp += dp[iid[i]][(1<<child[iid[i]].size())-1];
for(int j = i; j<cnt; j++){
if(!(mask&(1<<j))) continue;
int mi = ((1<<cnt)-1)^(1<<i), mj = ((1<<cnt)-1)^(1<<j);
if(dp[v][mask&mi&mj] == -1) continue;
dp[v][mask] = max(dp[v][mask], lol[i][j]+dp[v][mask&mi&mj]);
}
}
dp[v][mask] = max(dp[v][mask], tmp);
}
}
int main(){
// freopen("a.in", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for(int i = 0; i<m; i++){
int a, b, w; cin >> a >> b >> w; --a; --b;
if(!w)
adj[a].push_back(b),
adj[b].push_back(a);
else
edges.push_back({a, b, w});
}
dfs1(0, 0);
m = edges.size();
for(int i = 0; i<m; i++){
int a = edges[i][0], b = edges[i][1], w = edges[i][2];
ans += w;
if(dep[a]%2 != dep[b]%2) continue;
tmpe.push_back(edges[i]);
}
swap(tmpe, edges);
m = edges.size();
for(int i = 0; i<m; i++){
auto e = edges[i];
int a = e[0], b = e[1];
paths[LCA(a, b)].push_back(i);
}
dfs2(0, 0);
cout << ans-dp[0][(1<<child[0].size())-1] << endl;
}
# | 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... |