oToToT的code收藏區

題目連結: http://tioj.infor.org/problems/1163 本題看似給定一張無向圖，實在不好求得所有路徑最大值的最小值，但是很明顯可以發現因為是要最小的最大值，所以其實先把最小生成樹找出來後，再在上面求路徑最大值就會是好的，而且如果是寫kruskal演算法，你還可以快速知道兩個點是不是連通的。而要求一棵樹上路徑的最大值，不難發現你可以把路徑拆成a到LCA(a,b)跟b到LCA(a,b) (其中LCA指的是最低共同祖先)，然後通常求LCA時會用倍增法，而這時就會發現其實求路徑最大值也可以用倍增法，一樣每次更新這段的最大值，然後找的時候也差不多。 p.s 比較好的講法可以看 這篇 #include <bits/stdc++.h> using namespace std; #define N 30000 #define logN 16 typedef pair<int,int> PII; int djs[N+5]; int Query(int x){if(djs[x]!=x)djs[x]=Query(djs[x]);return djs[x];} inline void Merge(int a,int b){djs[Query(a)]=Query(b);} struct Edge{ int s,e,p; bool operator>(const Edge& x)const{return p>x.p;} }; vector<PII> Tree[N+5]; int time_in[N+5], time_out[N+5],timer=0; PII ff[N+1][logN+1]; void dfs(int,int,int); inline bool anc(int,int); inline int lca(int,int); inline int getMax(int,int); bitset<N+5> walked; int main(){ ios_base::s...

題目連結: http://codeforces.com/problemset/problem/609/E 本題跟次小生成樹的做法大同小異，畢竟要做 次小生成樹 就要求MST for each edge，所以就按照次小生成樹的做法稍微改一改吧。 #include <bits/stdc++.h> using namespace std; typedef long long lld; typedef pair<int,lld> pil; #define N 200000 #define logN 20 struct Edge{ int s,e,id; lld w; Edge(){} Edge(int a,int b,lld c,int d){s=a;e=b;w=c;id=d;} bool operator<(const Edge& a){return w<a.w;} }; int djs[N+1]; vector<Edge> Es; int Query(int x){if(djs[x]!=x)djs[x]=Query(djs[x]);return djs[x];}; inline void Merge(int a,int b){djs[Query(a)]=Query(b);} vector<pil> MST[N+5]; pil ff[N+1][logN+1]; int time_in[N+5],time_out[N+5],timer=0; void dfs(int,int,lld); inline int lca(int,int); inline bool anc(int,int); inline lld walk(int,int); lld ans[N+5]; int main(){ cin.tie(0);ios_base::sync_with_stdio(0); int n,m; ...

題目連結: http://tioj.infor.org/problems/1445 不難發現本題就是是一題裸次小生成樹題，那次小生成樹該怎麼寫呢？先求一棵最小生成樹後，枚舉所有不在最小生成樹上的邊，把它塞到最小生成樹上，此時必定會產生一個環，而把在環上且在最小生成樹上的最大邊拔掉後就得到了另一個生成樹，不難證明枚舉完這些樹後得到的答案就會是次小生成樹。不過要怎麼有效率的求一個路徑上的最大值呢？不難想到可以樹練剖分，不過礙於記憶體限制，我不太確定會不會MLE。不過想想後如果你是用倍增法求LCA的話，在跑上去的過程中似乎就可以順便算最大值，所以就先求LCA後，再對兩個點倍增到LCA，並同時算最大值就可以解決這問題了。複雜度：$O(E log E)$ #include <bits/stdc++.h> using namespace std; #define endl '\n' #define PB push_back typedef long long lld; typedef pair<lld,lld> pll; #define N 1000 #define logN 15 #define INF 2147483647777 struct Edge{ int s,e; lld v; }; int djs[N+5]; inline int Query(int); inline void Merge(int,int); vector<Edge> Tree; vector<pll> MST[N+5]; pll ff[N+5][logN+5]; int timer=0,time_in[N+5],time_out[N+5]; void dfs(lld,lld,lld); inline bool anc(int,int); inline int lca(int,int); inline lld walk(int,int); int main(){ cin.tie(0);io...