2599: [IOI2011]Race

Time Limit: 70 Sec??Memory Limit: 128 MB
Submit: 2590??Solved: 769
[Submit][Status][Discuss]

Description

給一棵樹,每條邊有權.求一條簡單路徑,權值和等于K,且邊的數量最小.N <= 200000, K <= 1000000

Input

第一行 兩個整數 n, k
第二..n行 每行三個整數 表示一條無向邊的兩端和權值 (注意點的編號從0開始)

Output

一個整數 表示最小邊數量 如果不存在這樣的路徑 輸出-1

Sample Input

4 3
0 1 1
1 2 2
1 3 4

Sample Output

2

HINT

$N<=200000,K<=1000000$

Source

Solution

樹的點分治裸題，但是做法有點有趣

開始考慮的是：

正常的點分，然后每次用當前根開始BFS子樹，以獲得子樹中每個節點到根的邊權和和路徑長度，并利用之前的結果和當前結果更新答案

不過貌似寫掛了50s左右炸掉- -

發現其實不需要，只需要開一個100W的數組來記錄 當前到根的距離為$i$的路徑長度最短值

這樣就可以不斷對子樹進行更新和對答案進行更新了

時間復雜度依舊是$O(nlogn)$

Code

#include<iostream> #include<cmath> #include<cstring> #include<algorithm> #include<cstdio> using namespace std; int read() {int x=0,f=1; char ch=getchar();while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}return x*f; } #define maxn 200010 #define maxk 1000010 #define inf 0x3f3f3f3f int n,K; struct EdgeNode{int next,to,val;}edge[maxn<<1]; int head[maxn],cnt=1; void add(int u,int v,int w) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v; edge[cnt].val=w;} void insert(int u,int v,int w) {add(u,v,w); add(v,u,w);} int size[maxn],maxx[maxn],num[maxk],siz,root,ans; bool visit[maxn]; void Getroot(int now,int last) {size[now]=1; maxx[now]=0;for (int i=head[now]; i; i=edge[i].next)if (edge[i].to!=last && !visit[edge[i].to]){Getroot(edge[i].to,now);size[now]+=size[edge[i].to];maxx[now]=max(maxx[now],size[edge[i].to]);}maxx[now]=max(maxx[now],siz-size[now]);if (maxx[now]<maxx[root]) root=now; } struct Node{int d,t;}st[maxn]; int s,top; void DFS(int now,int dis,int tt,int last) {if (dis>K) return;ans=min(ans,tt+num[K-dis]);st[top++]=Node{dis,tt};for (int i=head[now]; i; i=edge[i].next)if (edge[i].to!=last && !visit[edge[i].to])DFS(edge[i].to,dis+edge[i].val,tt+1,now); } void Solve(int now) {root=0; Getroot(now,0); now=root;s=0,top=0;for (int i=head[now]; i; i=edge[i].next)if (!visit[edge[i].to]){DFS(edge[i].to,edge[i].val,1,now);for (int j=s; j<=top-1; j++)num[st[j].d]=min(num[st[j].d],st[j].t);s=top;}for (int i=0; i<=top-1; i++) num[st[i].d]=inf; num[0]=0;visit[now]=1;for (int i=head[now]; i; i=edge[i].next)if (!visit[edge[i].to])siz=size[edge[i].to],Solve(edge[i].to); } int main() {n=read(); K=read();for (int u,v,w,i=1; i<=n-1; i++) u=read()+1,v=read()+1,w=read(),insert(u,v,w);memset(num,inf,sizeof(num)); num[0]=0;ans=inf;siz=maxx[0]=n; Solve(1);if (ans!=inf) {printf("%d\n",ans); return 0;}puts("-1");return 0; }

AC第一道IOI ? ovo!

轉載于:https://www.cnblogs.com/DaD3zZ-Beyonder/p/5618633.html

總結

以上是生活随笔為你收集整理的【BZOJ-2599】Race 点分治的全部內容，希望文章能夠幫你解決所遇到的問題。

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