Brief description:
。。。 n 個結點的帶容量無向樹,m 個詢問。
每個詢問形如 (s, t, k, a, b)。。表示。。
。。允許已 a 的代價修建一條單位容量的新邊,b 的代價將一條舊邊或新邊增加單位流量。。
。。預算為 k 時 s->t 的最大流。。
Analysis:
。。先考慮加邊的情況。。如果要加邊的話。。只會加在 s->t
上。。。
。。如果a <= b
。。那麼狂加邊就行了。。。否則的話。。只會添加一條邊。。且擴容操作全部給這條邊最優。
。。接下來考慮不加邊的情況。。取出 s->t
路徑上的所有邊權。。在預算範圍內儘可能讓紅線畫的更高。。推更多的流。。。。顯然這是樹上區間 kth 問題。。。可以使用主席樹。。。。
本來主席樹求 kth 大是只帶一個 logn 的。。。我比賽的時候搞著搞著又搞成二分那條紅線了。又把第二個 logn 加回來艹。。。
。。。。
。。言歸正傳。。。對於求 s->t 的初始 flow 的過程。。就是求這個路徑上 rmq。。。
。。現在反正有了主席樹那麼求初始流可以用 kth()
。。解決。(這裡 k 固定為 1)。。。
。。在預算範圍至多還能推多少流的函數我們記作 kth2()
。。這裡的 "k" 表示預算。。在這個函數的末尾。。求出流量後我們立刻返回收益。。
。。(注意。。主席樹的值域我們只開到 10000.。 所以可能返回收益的時刻還有沒有花完的預算。。還可以繼續加上。。
。。。。需要維護。。。
。c[]:個數。。以及
。d[]:和。。
const int N = 100009, M = 2 * N, LM = 18; int hd[N], suc[M], to[M], wt[N]; int ST[LM][M], st[N], dep[N]; // Euler index ... int n, tt; int T[N], Null; const int NN = 20 * N; int l[NN], r[NN], c[NN], d[NN], total; // Chairman tree #define lx l[x] #define rx r[x] #define ly l[y] #define ry r[y] #define cx c[x] #define cy c[y] #define ml (ll+rr>>1) #define mr (ml+1) #define lc lx, ll, ml #define rc rx, mr, rr #define lt lx = ++total, rx = ry, x = lx, y = ly, rr = ml #define rt lx = ly, rx = ++total, x = rx, y = ry, ll = mr int Tn; int new_node(){ ++total; l[total] = r[total] = c[total] = d[total] = 0; return total; } int Insert(int y, int p){ int x = new_node(), root = x, ll = 0, rr = Tn; c[x] = c[y] + 1, d[x] = d[y] + p; while (ll < rr){ if (p < mr) lt; else rt; c[x] = c[y] + 1, d[x] = d[y] + p; } return root; } inline bool elder(int a, int b){ return dep[a] < dep[b]; } inline int lca(int a, int b){ int l = st[a], r = st[b]; if (l > r) swap(l, r); ++r; int lv = lg2(r-l); //log2(r - l); return min(ST[lv][l], ST[lv][r-(1<<lv)], elder); } #define aa to[i^1] #define bb to[i] #define v bb #define ww wt[i/2] void dfs(int u = 1){ ST[0][st[u] = ++tt] = u; REP_G(i, u) if (!st[v]){ dep[v] = dep[u] + 1, T[v] = Insert(T[u], ww); dfs(v); ST[0][++tt] = u; } } int kth2(int x, int y, int k){ int z = lca(x, y); x = T[x], y = T[y], z = T[z]; int ll = 0, rr = Tn, t, cc = 0, dd = 0; int D = c[x] + c[y] - 2*c[z], tc, td; while (ll < rr){ if (ml * (cc + (tc = c[lx] + c[ly] - 2*c[l[z]])) - (dd + (td = d[lx] + d[ly] - 2*d[l[z]])) >= k){ x = l[x], y = l[y], z = l[z]; rr = ml; } else { x = r[x], y = r[y], z = r[z]; cc += tc, dd += td, ll = mr; } } if ((k-((cc*ll)-dd))<0) --ll; return ll + (k-((cc*ll)-dd))/D; } int kth(int x, int y, int k){ int z = lca(x, y); x = T[x], y = T[y], z = T[z]; int ll = 0, rr = Tn, t; while (ll < rr){ if ((t = c[l[x]] + c[l[y]] - 2*c[l[z]]) >= k){ x = l[x], y = l[y], z = l[z]; rr = ml; } else { x = r[x], y = r[y], z = r[z]; k -= t, ll = mr; } } return ll; } int main(){ #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out2.txt", "w", stdout); #endif Rush{ printf("Case #%d:\n", ++Case); int Q; RD(n, Q); fill(hd+1, hd+n+1, 0); fill(st+1, st+n+1, 0); Tn = 0; FOR_C(i, 2, n << 1){ RD(to[i], to[i|1]); checkMax(Tn, RD(ww)); suc[i] = hd[aa], hd[aa] = i++; suc[i] = hd[aa], hd[aa] = i; } total = 0, T[1] = new_node(); tt = 0, dfs(); for ( int lv = 1 ; _1(lv) <= tt ; lv ++ ){ for ( int i = 1 ; i + _1(lv) <= tt + 1 ; i ++ ) ST[lv][i] = min(ST[lv-1][i], ST[lv-1][i + _1(lv-1)], elder); } DO(Q){ int s, t, k, a, b; RD(s, t, k, a, b); int flow = kth(s, t, 1), res = a <= b ? k/a + flow : max((k>=a?(k-a)/b+1:0) + flow, kth2(s, t, k/b)); printf("%d\n", res); } } }
External link:
https://gist.github.com/lychees/6562208
https://www.shuizilong.com/house/archives/spoj-10628-count-on-a-tree/