其实是求树上的路径间的数据第K大的题目。
果断主席树 + LCA。
初始流量是这条路径上的最小值。
若a<=b，显然直接为s->t建立pipe可以使流量最优；
否则，对【0, 10**4】二分得到boundry，使得boundry * n_edge - sum_edge <= k/b， 或者建立s->t，然后不断extend s->t。
/* 4729 */
#include <iostream>
#include <sstream>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <cctype>
#include <cassert>
#include <functional>
#include <iterator>
#include <iomanip>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,1024000") #define sti set<int>
#define stpii set<pair<int, int> >
#define mpii map<int,int>
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define rep(i, a, n) for (int i=a;i<n;++i)
#define per(i, a, n) for (int i=n-1;i>=a;--i)
#define clr clear
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
// #define lson l, mid, rt<<1
// #define rson mid+1, r, rt<<1|1 typedef struct {
int v, c, nxt;
} edge_t; const int maxn = 1e5+;
const int m = ;
const int maxm = maxn * ;
int T[maxn];
int lson[maxm], rson[maxm], c[maxm], sum[maxm];
int head[maxn], l;
edge_t E[maxn<<];
int tot, n, q;
int beg[maxn];
int V[maxn<<], D[maxn<<], top;
int dp[][maxn<<]; void init() {
memset(head, -, sizeof(head));
l = top = ;
tot = ;
} int Build(int l, int r) {
int rt = tot++; c[rt] = sum[rt] = ;
if (l == r)
return rt; int mid = (l + r) >> ; lson[rt] = Build(l, mid);
rson[rt] = Build(mid+, r); return rt;
} int Insert(int rt, int x, int val) {
int nrt = tot++, ret = nrt;
int l = , r = m - , mid; c[nrt] = c[rt] + ;
sum[nrt] = sum[rt] + val;
while (l < r) {
mid = (l + r) >> ;
if (x <= mid) {
lson[nrt] = tot++;
rson[nrt] = rson[rt];
nrt = lson[nrt];
rt = lson[rt];
r = mid;
} else {
lson[nrt] = lson[rt];
rson[nrt] = tot++;
nrt = rson[nrt];
rt = rson[rt];
l = mid + ;
}
c[nrt] = c[rt] + ;
sum[nrt] = sum[rt] + val;
} return ret;
} int Query_kth(int urt, int vrt, int frt, int k) {
int l = , r = m - , mid;
int tmp; while (l < r) {
mid = (l + r) >> ;
tmp = c[lson[urt]] + c[lson[vrt]] - (c[lson[frt]] << );
if (tmp >= k) {
urt = lson[urt];
vrt = lson[vrt];
frt = lson[frt];
r = mid;
} else {
k -= tmp;
urt = rson[urt];
vrt = rson[vrt];
frt = rson[frt];
l = mid + ;
}
} return l;
} int Query_Bound(int urt, int vrt, int frt, int delta) {
int l = , r = m - , mid;
int cc = , csum = ;
int tc, tsum;
int ans = , tmp; while (l < r) {
mid = (l + r) >> ;
tc = c[lson[urt]] + c[lson[vrt]] - (c[lson[frt]] << );
tsum = sum[lson[urt]] + sum[lson[vrt]] - (sum[lson[frt]] << );
tmp = mid*(tc+cc)-(tsum+csum);
if (tmp <= delta)
ans = max(ans, mid);
if (mid*(tc+cc)-(tsum+csum) >= delta) {
urt = lson[urt];
vrt = lson[vrt];
frt = lson[frt];
r = mid;
} else {
urt = rson[urt];
vrt = rson[vrt];
frt = rson[frt];
cc += tc;
csum += tsum;
l = mid + ;
}
} return ans;
} void addEdge(int u, int v, int c) {
E[l].v = v;
E[l].c = c;
E[l].nxt = head[u];
head[u] = l++; E[l].v = u;
E[l].c = c;
E[l].nxt = head[v];
head[v] = l++;
} void dfs(int u, int fa, int dep) {
int v, k; V[++top] = u;
D[top] = dep;
beg[u] = top; for (k=head[u]; k!=-; k=E[k].nxt) {
v = E[k].v;
if (v == fa)
continue;
T[v] = Insert(T[u], E[k].c, E[k].c);
dfs(v, u, dep+);
V[++top] = u;
D[top] = dep;
}
} void Init_RMQ(int n) {
int i, j; for (i=; i<=n; ++i)
dp[][i] = i;
for (j=; (<<j)<=n; ++j)
for (i=; i+(<<j)-<=n; ++i)
if (D[dp[j-][i]] < D[dp[j-][i+(<<(j-))]])
dp[j][i] = dp[j-][i];
else
dp[j][i] = dp[j-][i+(<<(j-))];
} int RMQ(int l, int r) {
if (l > r)
swap(l, r); int k = ; while (<<(k+) <= r-l+)
++k; if (D[dp[k][l]] < D[dp[k][r-(<<k)+]])
return V[dp[k][l]];
else
return V[dp[k][r-(<<k)+]];
} void solve() {
T[] = Build(, m - );
dfs(, , );
Init_RMQ(top); int u, v, k, a, b;
int lca;
int ans, tmp, org; while (q--) {
scanf("%d %d %d %d %d", &u, &v, &k, &a, &b);
lca = RMQ(beg[u], beg[v]);
org = Query_kth(T[u], T[v], T[lca], );
#ifndef ONLINE_JUDGE
// printf("f = %d\n", lca);
#endif
if (a <= b) {
ans = org + k / a;
} else {
ans = org;
if (k >= a)
ans += + (k-a)/b;
tmp = Query_Bound(T[u], T[v], T[lca], k/b);
#ifndef ONLINE_JUDGE
// printf("org = %d, ans = %d, bound = %d\n", org, ans, tmp);
#endif
ans = max(ans, tmp);
}
printf("%d\n", ans);
}
} int main() {
ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif int t;
int u, v, c; scanf("%d", &t);
rep(tt, , t+) {
init();
scanf("%d %d", &n, &q);
rep(i, , n) {
scanf("%d %d %d", &u, &v, &c);
addEdge(u, v, c);
}
printf("Case #%d:\n", tt);
solve();
} #ifndef ONLINE_JUDGE
printf("time = %d.\n", (int)clock());
#endif return ;
}
数据发生器。
from copy import deepcopy
from random import randint, shuffle
import shutil
import string def GenDataIn():
with open("data.in", "w") as fout:
t = 10
bound = 10**4
fout.write("%d\n" % (t))
for tt in xrange(t):
n = randint(100, 200)
q = randint(100, 200)
fout.write("%d %d\n" % (n, q))
ust = [1]
vst = range(2, n+1)
for i in xrange(1, n):
idx = randint(0, len(ust)-1)
u = ust[idx]
idx = randint(0, len(vst)-1)
v = vst[idx]
ust.append(v)
vst.remove(v)
c = randint(0, bound-1)
fout.write("%d %d %d\n" % (u, v, c))
for i in xrange(q):
u = randint(1, n)
while True:
v = randint(1, n)
if v!=u:
break
k = randint(0, bound)
a = randint(1, bound)
b = randint(1, bound)
fout.write("%d %d %d %d %d\n" % (u, v, k, a, b)) def MovDataIn():
desFileName = "F:\eclipse_prj\workspace\hdoj\data.in"
shutil.copyfile("data.in", desFileName) if __name__ == "__main__":
GenDataIn()
MovDataIn()