發展城市

Time Limit: 20 Sec??Memory Limit: 512 MB
[Submit][Status][Discuss]

Description

　　眾所周知，Hzwer學長是一名高富帥，他打算投入巨資發展一些小城市。
　　Hzwer打算在城市中開N個賓館，由于Hzwer非常壕，所以賓館必須建在空中，但是這樣就必須建立賓館之間的連接通道。機智的Hzwer在賓館中修建了N-1條隧道，也就是說，賓館和隧道形成了一個樹形結構。
　　Hzwer有時候會花一天時間去視察某個城市，當來到一個城市之后，Hzwer會分析這些賓館的顧客情況。對于每個顧客，Hzwer用三個數值描述他：（S， T， V）表示該顧客這天想要從賓館S走到賓館T，他的速度是V。
　　Hzwer需要做一些收集一些數據，這樣他就可以規劃他接下來的投資。
　　其中有一項數據就是收集所有顧客可能的碰面次數。
　　每天清晨，顧客同時從S出發以V的速度前往T（注意S可能等于T），當到達了賓館T的時候，顧客顯然要找個房間住下，那么別的顧客再經過這里就不會碰面了。特別的，兩個顧客同時到達一個賓館是可以碰面的。同樣，兩個顧客同時從某賓館出發也會碰面。

Input

?　　第一行一個正整數T(1<=T<=20)，表示Hzwer發展了T個城市，并且在這T個城市分別視察一次。
?　　對于每個T，第一行有一個正整數N(1<=N<=10^5)表示Hzwer在這個城市開了N個賓館。
?　　接下來N-1行，每行三個整數X，Y，Z表示賓館X和賓館Y之間有一條長度為Z的隧道
?　　再接下來一行M表示這天顧客的數量。
?　　緊跟著M行每行三個整數（S， T， V）表示該顧客會從賓館S走到賓館T，速度為v

Output

　　 對于每個T，輸出一行，表示顧客的碰面次數。

Sample Input

　　2
　　3
　　1 2 1
　　2 3 1
　　3
　　1 3 2
　　3 1 1
　　1 2 3
　　1
　　0

Sample Output

　　2
　　0

HINT

　　1<=T<=20?? 1<=N<=10^5?? 0<=M<=10^3?? 1<=V<=10^6?? 1<=Z<=10^3

Main idea

　　給定若干個顧客，每個顧客會勻速從一個點走到另外一個點，問有幾對人會在路上相遇。

Solution

　　由于人數較少，所以我們可以O(m^2)判斷兩人是否相交。

　　首先，兩個人相遇只可能是在路徑重疊的部分相遇，所以我們先對兩人的路徑求交，這里提供一種對樹上路徑求交的方法：

　　　　求出AB兩人路徑的交：
　　　　　　設A路徑為a.u->a.v，B路徑為b.u->b.v。那么我們求出 LCA(a.u,b.u)，LCA(a.v,b.v)，LCA(a.u,b.v)，LCA(b.u,a.v)，然后保留下在AB路徑上的點。（判斷一個點是否在路徑上：若u在LCA(x,y)的子樹中，且u為LCA(u,x)或者LCA(u,y)，則u在路徑x,y上），然后按照dfs序位置排序，去重，保留下后兩個點，則后兩個點即是路徑的端點。

　　但是這樣求交的話需要多次查詢LCA，我們用每次log的時間查詢顯然會超時，于是我們引進O(nlog(n))預處理，O(1)查詢的LCA。

　　　　O(1)查詢的LCA：
　　　　　　我們先求出對于這棵樹的歐拉序（歐拉序：記下每個點第一次訪問的位置以及回溯完的位置），然后我們用那么這時候x,y之間的LCA也就是 [pos[x],pos[y]] 區間內深度最小的點（pos[x]表示點x第一次在歐拉序中出現的位置），這個區間最小值用RMQ求即可。

　　現在我們已經求出了路徑的交集，然后我們暴力分類討論一下。如果沒有交集則必然不相交，若交于一點判斷一下到達時間即可，否則：

　　先考慮兩人運動的方向。我們記錄p.u,p.v表示路徑交集的兩個端點。A1表示A到先進入路徑的端點，A2表示A后到的端點，B1、B2類似（用距離長短判斷即可），如果A1=B1則表示兩人同向運動，否則表示相向運動。然后我們討論一下：

　　　　同向運動：如果兩人同向運動，那么若先進入路徑的后離開路徑，則兩人會相遇。
　　　　相向運動：如果兩人相向運動，則我們記錄到端點的時間，如果兩個人在路徑上的時間有交集的話，則會相遇。

　　然后這樣判斷一下就可以求出答案了，但是由于double定義下的除法速度很慢，會被卡常數，所以我們再用在long long定義下的交叉相乘來判斷以上情況。這樣我們就解決了這道題\(≧▽≦)/

Code

1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<cstring> 5 #include<cstdlib> 6 #include<cmath> 7 using namespace std; 8 typedef long long s64; 9 10 const int ONE = 100005; 11 12 int T; 13 int n,m; 14 int x,y,z; 15 int next[ONE*2],first[ONE],go[ONE*2],w[ONE*2],tot; 16 int pos[ONE],dfn_cnt,Dep[ONE],size[ONE]; 17 int MinD[ONE*2][18],NumD[ONE*2][18]; 18 int Log[ONE*2],Bin[18]; 19 int Stk[5],top,fc; 20 int Ans; 21 s64 d[ONE]; 22 23 struct power 24 { 25 int u,v; 26 int val; 27 }a[1005],p; 28 29 namespace input 30 { 31 const int BufferSize = 1 << 16 | 1; 32 33 char buffer[BufferSize]; 34 char *head = buffer + BufferSize; 35 const char *tail = head; 36 37 inline char nextChar() 38 { 39 if (head == tail) 40 { 41 fread(buffer, 1, BufferSize, stdin); 42 head = buffer; 43 } 44 return *head++; 45 } 46 47 inline int get() 48 { 49 static char c; 50 while ((c = nextChar()) < '0' || c > '9'); 51 52 int res = c - '0'; 53 while ((c = nextChar()) >= '0' && c <= '9') 54 res = res * 10 + c - '0'; 55 return res; 56 } 57 } 58 using input::get; 59 60 inline void Add(int u,int v,int z) 61 { 62 next[++tot]=first[u]; first[u]=tot; go[tot]=v; w[tot]=z; 63 next[++tot]=first[v]; first[v]=tot; go[tot]=u; w[tot]=z; 64 } 65 66 namespace F 67 { 68 int Dfs(int u,int father) 69 { 70 pos[u] = ++dfn_cnt; 71 Dep[u] = Dep[father] + 1; 72 size[u] = 1; 73 MinD[dfn_cnt][0]=Dep[u]; NumD[dfn_cnt][0]=u; 74 for(int e=first[u];e;e=next[e]) 75 { 76 int v=go[e]; 77 if(v==father) continue; 78 d[v] = d[u] + w[e]; 79 Dep[v] = Dep[u] + 1; 80 Dfs(v,u); 81 size[u] += size[v]; 82 MinD[++dfn_cnt][0]=Dep[u]; NumD[dfn_cnt][0]=u; 83 } 84 } 85 86 inline void Pre_Rmq() 87 { 88 for(int j=1;j<=17;j++) 89 for(int i=1;i<=dfn_cnt;i++) 90 if(i+Bin[j]-1 <= dfn_cnt) 91 { 92 int Next = i + Bin[j-1]; 93 if(MinD[i][j-1] < MinD[Next][j-1]) 94 MinD[i][j]=MinD[i][j-1], NumD[i][j]=NumD[i][j-1]; 95 else 96 MinD[i][j]=MinD[Next][j-1], NumD[i][j]=NumD[Next][j-1]; 97 } 98 else break; 99 } 100 } 101 102 inline int LCA(int x,int y) 103 { 104 x=pos[x]; y=pos[y]; 105 if(x > y) swap(x,y); 106 int T = Log[y - x +1]; 107 if(MinD[x][T] < MinD[y-Bin[T]+1][T]) return NumD[x][T]; 108 return NumD[y-Bin[T]+1][T]; 109 } 110 111 inline s64 dist(int x,int y) 112 { 113 return d[x] + d[y] - (d[LCA(x,y)] << 1) ; 114 } 115 116 namespace PD 117 { 118 inline bool inroad(int u,power a) 119 { 120 int lca = LCA(a.u,a.v); 121 if(LCA(u,lca) != lca) return 0; 122 return (LCA(u,a.u)==u || LCA(u,a.v)==u); 123 } 124 } 125 126 inline void Sort(int n) 127 { 128 for(int i=1;i<=n;i++) 129 for(int j=i+1;j<=n;j++) 130 if(pos[Stk[i]] > pos[Stk[j]]) 131 swap(Stk[i], Stk[j]); 132 } 133 134 inline power Get_road(power a,power b) 135 { 136 fc=top=0; 137 Stk[++fc] = LCA(a.u,b.u); Stk[++fc] = LCA(a.v,b.v); 138 Stk[++fc] = LCA(a.u,b.v); Stk[++fc] = LCA(b.u,a.v); 139 for(int i=1;i<=fc;i++) 140 if(PD::inroad(Stk[i],a) && PD::inroad(Stk[i],b)) 141 Stk[++top] = Stk[i]; 142 143 Sort(top); 144 top=unique(Stk+1,Stk+top+1) - Stk - 1; 145 146 power p; p.val = 0; 147 if(top==0) p.u = p.v = 0; 148 if(top==1) p.u = p.v = Stk[1]; 149 if(top==2) p.u=Stk[1], p.v=Stk[2]; 150 if(top==3) p.u=Stk[2], p.v=Stk[3]; 151 return p; 152 } 153 154 inline bool pmin(s64 a,s64 b,s64 c) 155 { 156 if(a<=b && b<=c) return 1; 157 return 0; 158 } 159 160 inline int Deal(int x,int y) 161 { 162 if(a[x].u == a[y].u) return 1; 163 p = Get_road(a[x],a[y]); 164 if(p.u==p.v) 165 { 166 if(!p.u) return 0; 167 return (s64) dist(a[x].u,p.u) * a[y].val == (s64) dist(a[y].u,p.u) * a[x].val; 168 } 169 170 int A1,A2,B1,B2; 171 double A1_time,A2_time,B1_time,B2_time; 172 if(dist(a[x].u,p.u) < dist(a[x].u,p.v)) A1=p.u, A2=p.v;else A1=p.v, A2=p.u; 173 if(dist(a[y].u,p.u) < dist(a[y].u,p.v)) B1=p.u, B2=p.v;else B1=p.v, B2=p.u; 174 175 A1_time=(s64)dist(A1,a[x].u)*a[y].val; A2_time=(s64)dist(A2,a[x].u)*a[y].val; 176 B1_time=(s64)dist(B1,a[y].u)*a[x].val; B2_time=(s64)dist(B2,a[y].u)*a[x].val; 177 178 if(A1==B1)//same 179 { 180 if(A1_time == B1_time) return 1; 181 if(A1_time < B1_time) return A2_time >= B2_time; 182 return A2_time <= B2_time; 183 } 184 else 185 { 186 if(pmin(A1_time,B1_time,A2_time)) return 1; 187 if(pmin(A1_time,B2_time,A2_time)) return 1; 188 if(pmin(B1_time,A1_time,B2_time)) return 1; 189 if(pmin(B1_time,A2_time,B2_time)) return 1; 190 return 0; 191 } 192 } 193 194 inline void Solve() 195 { 196 n=get(); 197 dfn_cnt=tot=0; 198 memset(first,0,sizeof(first)); 199 for(int i=1;i<n;i++) 200 { 201 x=get(); y=get(); z=get(); 202 Add(x,y,z); 203 } 204 205 F::Dfs(1,0); F::Pre_Rmq(); 206 207 m=get(); 208 for(int i=1;i<=m;i++) 209 { 210 a[i].u=get(); a[i].v=get(); a[i].val=get(); 211 } 212 213 Ans = 0; 214 215 for(int i=1;i<=m;i++) 216 for(int j=i+1;j<=m;j++) 217 { 218 Ans += Deal(i,j); 219 } 220 221 printf("%d\n",Ans); 222 } 223 224 int main() 225 { 226 Log[0]=-1; for(int i=1;i<=2e5;i++) Log[i] = Log[i>>1] + 1; 227 Bin[0]=1; for(int i=1;i<=17; i++) Bin[i] = Bin[i-1] << 1; 228 229 T=get(); 230 231 while(T--) 232 Solve(); 233 } View Code

?

轉載于:https://www.cnblogs.com/BearChild/p/6531428.html

總結

以上是生活随笔為你收集整理的【BZOJ3700】发展城市 [LCA][RMQ]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。