NC21706. 牛牛的蜡烛
描述
输入描述
第一行输入一个整数n,表示树的总结点数
第二行输入n-1个整数ai
第三行输入n-1个整数bi
第四行输入n-1个整数ci
表示ai, bi 之间有一条长度为ci的蜡烛
2 ≤ n ≤ 20
0 ≤ ai ≤ n - 1
0 ≤ bi ≤ n - 1
1 ≤ ci ≤ 1000
输出描述
输出一个整数
示例1
输入:
3 0 1 1 2 10 1
输出:
2
示例2
输入:
4 0 0 0 1 2 3 1 1 1
输出:
2
示例3
输入:
4 0 0 0 1 2 3 1 2 3
输出:
4
示例4
输入:
9 0 1 1 2 3 3 2 4 1 2 3 4 5 6 7 8 5 3 2 4 6 8 7 1
输出:
7
C++(g++ 7.5.0) 解法, 执行用时: 332ms, 内存消耗: 23984K, 提交时间: 2023-03-12 19:26:25
#include<bits/stdc++.h>
#define _bt __builtin_
#define all(x) x.begin(),x.end()
#define x first
#define y second
#define i128 __int128
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define SZ(x) (int)x.size()
using namespace std;
typedef long long ll;
typedef array<int,2> ai2;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int N = 1e6+10,M = 2e3+10,mod=1e9+7,mod2=998244353,ba1=9999971,ba2=9999973;
const double eps = 1e-8;
mt19937 rng(time(0));
int n,m,k;
int a[N],b[N],c[N],d[N];
vector<PII> e[N];
priority_queue<PII,vector<PII>,greater<PII>> h;
int st[21],t[21];
void solve(){
cin >> n;
for(int i = 1; i < n; i ++) cin >> a[i];
for(int i = 1; i < n; i ++) cin >> b[i];
for(int i = 1; i < n; i ++){
cin >> c[i];
e[a[i]].push_back({b[i],c[i]});
e[b[i]].push_back({a[i],c[i]});
d[a[i]]++,d[b[i]]++;
}
set<int> ans;
auto cal = [&](int x){
int aa=t[a[x]],bb=t[b[x]],cc=c[x];
if(aa>bb) swap(aa,bb);
if(aa+cc<=bb) return 2*bb;
return cc-(bb-aa)+2*bb;
};
auto slove = [&](){
while(!h.empty()){
auto p = h.top();
h.pop();
if(st[p.y]) continue;
st[p.y] = 1;
for(auto [v,w] : e[p.y]){
if(st[v]) continue;
if(t[v] > p.x+w){
t[v] = p.x+w;
h.push({p.x+w,v});
}
}
}
int res = 0;
for(int i = 1; i < n; i ++){
res = max(res,cal(i));
}
ans.insert(res);
};
for(int i = 1; i < 1<<n; i ++){
memset(st,0,sizeof st);
memset(t,0x3f,sizeof t);
while(!h.empty()) h.pop();
int f=1;
for(int j = 0; j < n; j ++){
if(i & (1 << j)){
if(d[j]!=1){
f=0;
break;
}
h.push({0,j});
t[j]=0;
}
}
if(!f) continue;
else slove();
}
cout << SZ(ans) << endl;
}
int main()
{
int _=1;
IOS
//cin >> _;
//scanf("%d",&_);
for(int x=1;x<=_;x++){
solve();
}
return 0;
}
C++14(g++5.4) 解法, 执行用时: 414ms, 内存消耗: 2368K, 提交时间: 2020-10-06 09:26:55
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
#define MP make_pair
const int N = 21;
int n, tp;
int aa[N], bb[N], cc[N], tim[N], ans[1 << N];
bool vis[N];
vector<pair<int, int> > V[N];
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > Q;
int cal(int a, int b, int c) {
if (a > b) swap(a, b);
if (a + c <= b) return b * 2;
return b * 2 + (c - (b - a));
}
void solve() {
while (!Q.empty()) {
pair<int, int> x = Q.top();
Q.pop();
int u = x.second, t = x.first;
if (vis[u]) continue;
vis[u] = true;
tim[u] = t;
for (int i = 0; i < V[u].size(); i++) {
int v = V[u][i].first, c = V[u][i].second;
if (! vis[v] && tim[v] > tim[u] + c) {
tim[v] = tim[u] + c;
Q.push(MP(tim[u] + c, v));
}
}
}
int res = 0;
for (int i = 1; i < n; i++) {
res = max(res, cal(tim[aa[i]], tim[bb[i]], cc[i]));
}
ans[tp++] = res;
}
int main() {
//freopen("0.txt", "r", stdin);
scanf("%d", &n);
for (int i = 1; i < n; i++) scanf("%d", aa + i);
for (int i = 1; i < n; i++) scanf("%d", bb + i);
for (int i = 1; i < n; i++) scanf("%d", cc + i);
for (int i = 1; i < n; i++) {
V[aa[i]].push_back(MP(bb[i], cc[i]));
V[bb[i]].push_back(MP(aa[i], cc[i]));
}
Q.empty();
for (int i = 1; i < (1 << n); i++) {
memset(tim, 0x3f3f3f3f, sizeof(tim));
memset(vis, false, sizeof(vis));
bool flag = true;
for (int j = 0; j < n; j++) {
if (i & (1 << j)) {
if (V[j].size() != 1) flag = false;
tim[j] = 0;
Q.push(MP(0, j));
}
}
if (flag) solve();
else while (!Q.empty()) Q.pop();
}
sort(ans, ans + tp);
tp = unique(ans, ans + tp) - ans;
printf("%d\n", tp);
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 457ms, 内存消耗: 2424K, 提交时间: 2020-02-16 00:15:08
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
#define MP make_pair
const int N = 21;
int n, tp;
int aa[N], bb[N], cc[N], tim[N], ans[1 << N];
bool vis[N];
vector<pair<int, int> > V[N];
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > Q;
int cal(int a, int b, int c) {
if (a > b) swap(a, b);
if (a + c <= b) return b * 2;
return b * 2 + (c - (b - a));
}
void solve() {
while (!Q.empty()) {
pair<int, int> x = Q.top();
Q.pop();
int u = x.second, t = x.first;
if (vis[u]) continue;
vis[u] = true;
tim[u] = t;
for (int i = 0; i < V[u].size(); i++) {
int v = V[u][i].first, c = V[u][i].second;
if (! vis[v] && tim[v] > tim[u] + c) {
tim[v] = tim[u] + c;
Q.push(MP(tim[u] + c, v));
}
}
}
int res = 0;
for (int i = 1; i < n; i++) {
res = max(res, cal(tim[aa[i]], tim[bb[i]], cc[i]));
}
ans[tp++] = res;
}
int main() {
//freopen("0.txt", "r", stdin);
scanf("%d", &n);
for (int i = 1; i < n; i++) scanf("%d", aa + i);
for (int i = 1; i < n; i++) scanf("%d", bb + i);
for (int i = 1; i < n; i++) scanf("%d", cc + i);
for (int i = 1; i < n; i++) {
V[aa[i]].push_back(MP(bb[i], cc[i]));
V[bb[i]].push_back(MP(aa[i], cc[i]));
}
Q.empty();
for (int i = 1; i < (1 << n); i++) {
memset(tim, 0x3f3f3f3f, sizeof(tim));
memset(vis, false, sizeof(vis));
bool flag = true;
for (int j = 0; j < n; j++) {
if (i & (1 << j)) {
if (V[j].size() != 1) flag = false;
tim[j] = 0;
Q.push(MP(0, j));
}
}
if (flag) solve();
else while (!Q.empty()) Q.pop();
}
sort(ans, ans + tp);
tp = unique(ans, ans + tp) - ans;
printf("%d\n", tp);
return 0;
}