Topcoder Single Round Match 638 Div2 T3 CandleTimerEasy 题解

## Translation

• 只能从树的叶节点开始点燃；
• 长度为 len[i] 的蜡烛完全燃烧需要 len[i] 的时间。如果从它的两边同时点燃，则只需要 len[i]/2 的时间。

• A will contain between 1 and 19 elements, inclusive.
• A, B and len will contain same number of elements.
• Each element in A will be between 0 and |A|, inclusive.
• Each element in B will be between 0 and |A|, inclusive.
• Each element in len will be between 1 and 1000, inclusive.
• A, B and len will describe a tree.
• Time limit (s): 2.000
• Memory limit (MB): 256

## Examples

{0,1}
{1,2}
{10,1}

Returns: 2

This tree looks the same as a single candle of length 11. If we light it on one end, we will measure the time 11. If we light it on both ends, we will measure the time 5.5.

{0,0,0}
{1,2,3}
{1,1,1}

Returns: 2

This time we have 3 ends. If we ignite all of them the time is 1, otherwise the time is 2.

{0,0,0}
{1,2,3}
{1,2,3}

Returns: 4

We can get 4 different outcomes: 2.5, 3, 4, 5.

## Original

You have a lot of candles. The candles burn at a uniform rate: if you ignite a candle of length L, it will burn completely in L units of time. You can also ignite a candle at both ends, which makes it burn twice as fast. You have arranged some candles into the shape of a tree. You want to use the tree to measure time. At the beginning, you will ingite some leaves of the tree (all at the same time). Then you will just wait and watch the flames spread across the entire tree. (Whenever a flame reaches an inner node of the tree, it spreads to all branches that meet at that node.) Note that you are not allowed to light new flames during the process. The time you will measure is the time between the moment when you lighted the fire(s) and the moment when the last part of the tree finished burning. You are given a description of the tree as three vector s: a, b, and len, with N elements each. The nodes of the tree are numbered 0 through N, inclusive. For each valid i, there is a candle between the nodes a[i] and b[i] with length len[i]. Compute and return the number of different times you can measure when following the above procedure.

• 两端点中先烧到的一个，直接把整根蜡烛烧掉了，另一端的小火苗根本没有机会，则时间是：$min(t_{A_i},t_{B_i})+len_i$；
• 两端点中一个先开始烧这根蜡烛，烧了一会儿另外一端开始烧。那么较晚的一端开始烧的时候，剩下蜡烛长度是：$len_i-|t_{A_i}-t_{B_i}|$，这段只需要一半的时间；其余的一段则是需要完整的时间。烧完这根蜡烛总时间就是：max(t[A[i]],t[B[i]])+(len[i]-Abs(t[A[i]]-t[B[i]]))/2.0)

## Codes

#include <bits/stdc++.h>
#define CLEAR(x) memset(x,0,sizeof(x))
#define CLEAR_MAX(x) memset(x,63,sizeof(x))
using namespace std;
const int maxn=25,INF=1e8;
int n,s,ind[maxn];
int dst[maxn][maxn];
double t[maxn];
vector <double> vec;

class CandleTimerEasy {
public:
int differentTime( vector <int> A, vector <int> B, vector <int> len );
};
inline void init(){
vec.clear();CLEAR(ind);CLEAR_MAX(dst);
}
inline void Floyd(){
for (int i=0;i<n;i++) dst[i][i]=0;
for (int k=0;k<n;k++)
for (int i=0;i<n;i++) if (i!=k)
for (int j=0;j<n;j++) if ((j!=k)&&(j!=i))
dst[i][j]=dst[j][i]=min(dst[i][j],dst[i][k]+dst[k][j]);
}
inline double Abs(double x) {return x<0?-x:x;}
inline double Get(int x,vector <int> A, vector <int> B, vector <int> len){
double ret=0.0;
for (int i=0;i<n;i++) if ((ind[i]==1)&&(x&(1<<i))) t[i]=0; else {
t[i]=(double)INF;
for (int j=0;j<n;j++) if ((ind[j]==1)&&(x&(1<<j))&&(i!=j)) t[i]=min(t[i],(double)dst[i][j]);
ret=max(ret,t[i]);
}
for (int i=0;i<n-1;i++) ret=max(ret,min(min(t[A[i]],t[B[i]])+len[i],max(t[A[i]],t[B[i]])+(len[i]-Abs(t[A[i]]-t[B[i]]))/2.0));
return ret;
}
int CandleTimerEasy::differentTime(vector <int> A, vector <int> B, vector <int> len) {
init();
n=A.size()+1;s=1<<n;
for (int i=0;i<n-1;i++){
dst[A[i]][B[i]]=dst[B[i]][A[i]]=len[i];
ind[A[i]]++;ind[B[i]]++;
}
Floyd();
for (int i=1;i<s;i++) vec.push_back(Get(i,A,B,len));
sort(vec.begin(),vec.end());
int ans=0;
// for (int i=0;i<vec.size();i++) printf("ANS: %.3lf\n",vec[i]);
for (int i=0;i<vec.size();i++) if (((i==0)||(vec[i]!=vec[i-1]))&&(vec[i]>0)&&(vec[i]<INF)) ans++;//,printf("%.2f\n",vec[i]);
return ans;
}