BZOJ1977/LuoguP4180【模板】严格次小生成树[BJWC2010] （次小生成树）

小鱼儿 2021-11-17 05:10 188阅读 0赞

这道题本身思维难度不大，但综合性强，细节多  
在其上浪一个早上，你的  
**最小生成树 树链剖分 线段树 DEBUG能力**...  
都大幅提升  
细节与思路都在代码里面了。  
欢迎hack.

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define R(a,b,c) for(register int a = (b); a <= (c); ++a) #define nR(a,b,c) for(register int a = (b); a >= (c); --a) #define Max(a,b) ((a) > (b) ? (a) : (b)) #define Min(a,b) ((a) < (b) ? (a) : (b)) #define ll long long #define Fill(a,b) memset(a, b, sizeof(a)) //#define ON_DUBUG #ifdef ON_DUBUG #define D_e_Line printf("\n\n-------------------\n\n") #else #define D_e_Line ; #endif struct ios{ template<typename ATP>ios& operator >> (ATP &x){ x = 0; int f = 1; char c; for(c = getchar(); c < '0' || c > '9'; c=getchar()) if(c == '-') f = -1; while(c >= '0' && c <='9') x = x * 10 + (c ^ '0'), c = getchar(); x *= f; return *this; } }io; using namespace std; //#define TEST_INPUT #ifdef TEST_INPUT int main(){ while(1){ ll x; io >> x; cout << x << endl; } } #endif const int N = 100007; const int M = 300007; int n, m; struct Node{ int x,y,w,tag; bool operator < (const Node &b)const{ return w < b.w; } }a[M]; struct Edge{ int nxt,pre; long long w; }e[M<<1]; int head[N],cntEdge; inline void add(int u,int v,long long w){ e[++cntEdge] = (Edge){head[u], v, w}, head[u] = cntEdge; } long long MST; int f[N]; inline int Find(int x){ return x == f[x] ? x : f[x] = Find(f[x]); } inline void Kruskal(){ R(i,1,n) f[i] = i;//Always remember, Fool orphan! Get your father at the first time! sort(a + 1, a + m + 1); int tot = 1; R(i,1,m){ int p = Find(a[i].x), q =Find(a[i].y); if(p != q){ f[p] = q; MST += a[i].w; a[i].tag = true; if(++tot >= n) return; } } } int wSon[N]; int fa[N],son[N],siz[N],dep[N]; inline void DFS_First(int u,int father){ dep[u] = dep[father] + 1, siz[u] = 1, fa [u] = father; for(register int i = head[u]; i; i = e[i].nxt){ int v = e[i].pre; if(v == father) continue; DFS_First(v, u); siz[u] += siz[v]; if(!son[u] || siz[v] > siz[son[u]]){ son[u] = v; //Treat value(edge) as value(node) wSon[u] = e[i].w; } } } int top[N],rnk[N],dfn[N],dfnIndex; inline void DFS_Second(int u,int ancester,int w){ top[u] = ancester, dfn[u] = ++dfnIndex, rnk[dfnIndex] = w; if(!son[u]) return; DFS_Second(son[u], ancester, wSon[u]);//e[i].w or wSon[u] ? // The answer is wSon[u] because it's the weight of this node for(register int i = head[u]; i; i = e[i].nxt){ int v = e[i].pre; if(v != fa[u] && v != son[u]) DFS_Second(v, v, e[i].w);//e[i].w or wSon[u] ? // The answer is e[i].w because it's the cost to the next node. } } #define lson rt << 1, l, mid #define rson rt << 1 | 1, mid + 1, r struct SegmentTree{ int mx,sc; }t[M<<2]; inline void Pushup(int rt){ t[rt].mx = Max(t[rt<<1].mx, t[rt<<1|1].mx); t[rt].sc = Max(t[rt].mx != t[rt<<1].mx ? t[rt<<1].mx : t[rt<<1].sc, t[rt].mx != t[rt<<1|1].mx ? t[rt<<1|1].mx : t[rt<<1|1].sc); } inline void Build(int rt,int l,int r){ if(l == r){ t[rt].mx = rnk[l]; t[rt].sc = -1; //Pushup(rt);//Do there really need pushup? // No! You do not have to pull a tree you just put into the groud. return; } int mid = l + r >> 1; Build(lson), Build(rson); Pushup(rt); } SegmentTree Query(int rt,int l,int r,int L,int R){ if(L <= l && r <= R) return t[rt]; SegmentTree tmp_1, tmp_2, res; tmp_1.mx = tmp_1.sc = tmp_2.mx = tmp_2.sc;//Need initial? And why? /* There is a strange problem if I don't initial, the program will give a wrong answer. But if I write: tmp_1.mx = tmp_1.sc = tmp_2.mx = tmp_2.sc It'll be right. Pay attention, I do not write: tmp_1.mx = tmp_1.sc = tmp_2.mx = tmp_2.sc = 0 So what happend to this initial sentence? I believe you can find out by yourself. */ int mid = l + r >> 1; //D_e_Line; if(L <= mid) tmp_1 = Query(lson, L, R); if(mid < R) tmp_2 = Query(rson, L, R); res.mx = Max(tmp_1.mx, tmp_2.mx); res.sc = Max(res.mx != tmp_1.mx ? tmp_1.mx : tmp_1.sc, res.mx != tmp_2.mx ? tmp_2.mx : tmp_2.sc); return res; } inline long long QueryPath(int u,int v,long long w){ long long sum = 0; while(top[u] != top[v]){ if(dep[top[u]] < dep[top[v]]) u^=v^=u^=v; SegmentTree tmp = Query(1, 1, n, dfn[top[u]], dfn[u]); sum = Max(sum, tmp.mx != w ? tmp.mx : tmp.sc); u = fa[top[u]]; } if(u == v) return sum;//Is this so important? Is it the criminal of the endless of my program?//Well, for the second question, it may not. //And if I ignore it, it doesn't matter, but as it can make my program runs faster, why not? if(dep[u] < dep[v]) u^=v^=u^=v; SegmentTree tmp = Query(1, 1, n, dfn[v]+1, dfn[u]);//I'm not sure when I need use 'dfn[v]+1' sum = Max(sum, tmp.mx != w ? tmp.mx : tmp.sc); return sum; } int main(){ io >> n >> m; R(i,1,m){ int u,v,w; io >> u >> v >> w; a[i] = (Node){u, v, w, 0}; } Kruskal(); R(i,1,m){//Here ought to be m, not n! It's going through all the edges if(a[i].tag == true){ add(a[i].x, a[i].y, a[i].w); add(a[i].y, a[i].x, a[i].w); } } DFS_First(1, 0); DFS_Second(1, 0, 0); Build(1, 1, n); int sum = 2147483647; R(i,1,m){ if(a[i].tag == false){ sum = Min(sum, a[i].w - QueryPath(a[i].x, a[i].y, a[i].w)); } } printf("%lld\n", MST + sum); return 0; }

转载于:https://www.cnblogs.com/bingoyes/p/11175974.html