Problem Description

瑤瑤（tsyao）是某知名貨運公司（順豐）的老板，這個公司很大，貨物運輸量極大，因此公司修建了許多交通設施，掌控了一個國家的交通運輸。

這個國家有n座城市，公司的總部在1號城市。

公司下管轄的有m條道路和n-1段火車線路。

這m條道路和n-1條火車線路都可以用u來表示起點，v來表示終點（數據保證m條道路和n-1條火車線路構成有向無環圖）。

這n-1段火車道保證從1號城市出發，能夠有唯一的一道只包含火車道的線路到達其他n-1座城市。

每條道路和每段火車道都有一個最佳搭載貨物值ai，如果要搭載的貨物超過了ai，公司需要對經過該路線的超過ai的每單位貨物增加bi的維修費用，由于種種原因，如果搭載的貨物低于ai，公司需要對少的每單位貨物(設該路線有x的貨物，則計算為ai-x單位)增加ci的維修費用。當然，每單位貨物經過時，會有di的基礎維護費用。

這里有兩種操作：

C?xi?yi?zi：?隨著時間和環境的變化，火車道會受到一些影響，xi到yi的火車道ai會改變zi(新的ai應該為ai+zi)，若xi不能到達yi，則將hi到xi和hi到yi的路段ai改變zi(hi為可以到達xi和yi的城市，且不存在fi使得??hi能夠到達fi，fi能夠到達xi和yi)。

當某火車道的ai值小于0時，我們看做該條火車道的最佳搭載貨物值為0(當然ai事實上是負數)；

Q?vi?wi：?查詢當計劃將wi單位貨物從1號城市到vi號城市時，該公司需要的最小維護費用。維護費用計算為每條道路和火車道的維護費用的和(SUMbi+SUMci+SUMdi)。

Input

第一行兩個整數n，m，用空格隔開。

接下來n-1+m行，每行u，v，ai，bi，ci，di六個整數。

前n-1行表示火車線路，后m行表示道路。

接下來一行為一個整數q。

接下來q行分別為上述兩種操作。

Output

對于每次Q操作，輸出答案，數據保證答案在int范圍內。

?

題目大意：略。

思路：

——————————————————————————————————————————————————————————————————

扒官方題解：http://tsyao.tk/archives/94

對付修改的話，就用樹鏈剖分就好，然后每次詢問跑網絡流。

網絡流這樣建圖，先假設我每條邊都跑了0的流量，我們先算出跑了0的流量的費用，然后對于一條邊，我跑了小于ai的流量的時候，每次增加一點流量，就相當于減小了ci的費用，所以把一條邊拆成兩條邊，一條是費用為-ci+di，上界為ai的邊，一條是費用為bi+di，上界為無窮的邊。。。

——————————————————————————————————————————————————————————————————

PS：簡單的說就是兩條SB題合在一起出，這樣也脫離不了它是SB題的結果。但是卻忘了刪一條調試語句導致無限TLE……

?

代碼（1772MS）：

1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 #include <algorithm> 5 #include <queue> 6 using namespace std; 7 typedef long long LL; 8 9 const int MAXN = 510; 10 const int MAXV = MAXN; 11 const int MAXE = 2 * (2010 * 2 + MAXN * 2); 12 const int MAXT = MAXN << 2; 13 const int INF = 0x3f3f3f3f; 14 15 struct SPFA_COST_FLOW { 16 int head[MAXV]; 17 int to[MAXE], next[MAXE], cap[MAXE], flow[MAXE]; 18 LL cost[MAXE]; 19 int n, m, ecnt, st, ed; 20 21 void init(int n) { 22 this->n = n; 23 memset(head + 1, -1, n * sizeof(int)); 24 ecnt = 0; 25 } 26 27 void add_edge(int u, int v, int f, LL c) { 28 to[ecnt] = v; cap[ecnt] = f; cost[ecnt] = c; next[ecnt] = head[u]; head[u] = ecnt++; 29 to[ecnt] = u; cap[ecnt] = 0; cost[ecnt] = -c; next[ecnt] = head[v]; head[v] = ecnt++; 30 } 31 32 void clear() { 33 memset(flow, 0, ecnt * sizeof(int)); 34 } 35 36 LL dis[MAXV]; 37 int pre[MAXV]; 38 bool vis[MAXV]; 39 40 bool spfa() { 41 memset(vis + 1, 0, n * sizeof(bool)); 42 memset(dis, 0x3f, (n + 1) * sizeof(LL)); 43 queue<int> que; que.push(st); 44 dis[st] = 0; 45 while(!que.empty()) { 46 int u = que.front(); que.pop(); 47 vis[u] = false; 48 for(int p = head[u]; ~p; p = next[p]) { 49 int v = to[p]; 50 if(cap[p] - flow[p] && dis[u] + cost[p] < dis[v]) { 51 dis[v] = dis[u] + cost[p]; 52 pre[v] = p; 53 if(!vis[v]) { 54 que.push(v); 55 vis[v] = true; 56 } 57 } 58 } 59 } 60 return dis[ed] < dis[0]; 61 } 62 63 LL maxFlow, minCost; 64 65 LL min_cost_flow(int ss, int tt) { 66 st = ss, ed = tt; 67 maxFlow = minCost = 0; 68 while(spfa()) { 69 int u = ed, tmp = INF; 70 while(u != st) { 71 tmp = min(tmp, cap[pre[u]] - flow[pre[u]]); 72 u = to[pre[u] ^ 1]; 73 } 74 u = ed; 75 while(u != st) { 76 flow[pre[u]] += tmp; 77 flow[pre[u] ^ 1] -= tmp; 78 u = to[pre[u] ^ 1]; 79 } 80 maxFlow += tmp; 81 minCost += tmp * dis[ed]; 82 } 83 return minCost; 84 } 85 } G; 86 87 struct Tree { 88 struct Edge { 89 int a, b, c, d, u, v; 90 void read() { 91 scanf("%d%d%d%d%d%d", &u, &v, &a, &b, &c, &d); 92 } 93 } tree[MAXN], edge[MAXE]; 94 int tid[MAXN], eid[MAXN], size[MAXN], son[MAXN], top[MAXN], dep[MAXN], fa[MAXN]; 95 int n, m, q; 96 97 int head[MAXV], pre[MAXV], ecnt, dfs_clock; 98 int to[MAXE], next[MAXE], id[MAXE]; 99 LL add[MAXT]; 100 101 void init() { 102 memset(head + 1, -1, n * sizeof(int)); 103 ecnt = dfs_clock = 0; 104 } 105 106 void add_edge(int u, int v, int i) { 107 to[ecnt] = v; id[ecnt] = i; next[ecnt] = head[u]; head[u] = ecnt++; 108 to[ecnt] = u; id[ecnt] = i; next[ecnt] = head[v]; head[v] = ecnt++; 109 } 110 111 void dfs_size(int u, int f, int depth) { 112 size[u] = 1; dep[u] = depth; fa[u] = f; 113 int maxsize = son[u] = 0; 114 for(int p = head[u]; ~p; p = next[p]) { 115 int v = to[p]; 116 if(v == f) continue; 117 pre[v] = p; 118 dfs_size(v, u, depth + 1); 119 size[u] += size[v]; 120 if(size[v] > maxsize) { 121 maxsize = size[v]; 122 son[u] = v; 123 } 124 } 125 } 126 127 void dfs_heavy_edge(int u, int ancestor) { 128 tid[u] = ++dfs_clock; eid[dfs_clock] = id[pre[u]]; 129 top[u] = ancestor; 130 if(son[u]) dfs_heavy_edge(son[u], ancestor); 131 for(int p = head[u]; ~p; p = next[p]) { 132 int v = to[p]; 133 if(v == fa[u] || v == son[u]) continue; 134 dfs_heavy_edge(v, v); 135 } 136 } 137 138 #define ll (x << 1) 139 #define rr (ll | 1) 140 #define mid ((l + r) >> 1) 141 142 void pushdown(int x) { 143 if(add[x]) { 144 add[ll] += add[x]; 145 add[rr] += add[x]; 146 add[x] = 0; 147 } 148 } 149 150 void pushadd(int x, int l, int r) { 151 if(l == r) { 152 if(l > 1) tree[eid[l]].a += add[x]; 153 add[x] = 0; 154 } else { 155 pushdown(x); 156 pushadd(ll, l, mid); 157 pushadd(rr, mid + 1, r); 158 } 159 } 160 161 void modify(int x, int l, int r, int a, int b, int val) { 162 if(a <= l && r <= b) { 163 add[x] += val; 164 } else { 165 if(a <= mid) modify(ll, l, mid, a, b, val); 166 if(mid < b) modify(rr, mid + 1, r, a, b, val); 167 } 168 } 169 170 void modify(int x, int y, int val) { 171 while(top[x] != top[y]) { 172 if(dep[top[x]] < dep[top[y]]) swap(x, y); 173 modify(1, 1, n, tid[top[x]], tid[x], val); 174 x = fa[top[x]]; 175 } 176 if(x != y) { 177 if(dep[x] < dep[y]) swap(x, y); 178 modify(1, 1, n, tid[son[y]], tid[x], val); 179 } 180 } 181 182 int gid[MAXV]; 183 void initQuery() { 184 G.init(n + 1); 185 for(int i = 1; i < n; ++i) { 186 Edge &t = tree[i]; 187 gid[i] = G.ecnt; 188 G.add_edge(t.u, t.v, max(0, t.a), t.d - t.c); 189 G.add_edge(t.u, t.v, INF, t.d + t.b); 190 } 191 for(int i = 0; i < m; ++i) { 192 Edge &t = edge[i]; 193 G.add_edge(t.u, t.v, max(0, t.a), t.d - t.c); 194 G.add_edge(t.u, t.v, INF, t.d + t.b); 195 } 196 G.add_edge(n + 1, 1, 0, 0); 197 } 198 199 int query(int tt, int val) { 200 int ss = n + 1; 201 pushadd(1, 1, n); 202 LL sum = 0; 203 for(int i = 1; i < n; ++i) { 204 Edge &t = tree[i]; 205 sum += t.c * max(0, t.a); 206 G.cap[gid[i]] = max(0, t.a); 207 } 208 for(int i = 0; i < m; ++i) { 209 Edge &t = edge[i]; 210 sum += t.c * max(0, t.a); 211 } 212 G.cap[G.ecnt - 2] = val; 213 G.clear(); 214 return sum + G.min_cost_flow(ss, tt); 215 } 216 217 void work() { 218 scanf("%d%d", &n, &m); 219 for(int i = 1; i < n; ++i) tree[i].read(); 220 for(int i = 0; i < m; ++i) edge[i].read(); 221 init(); 222 initQuery(); 223 for(int i = 1; i < n; ++i) add_edge(tree[i].u, tree[i].v, i); 224 dfs_size(1, 0, 1); 225 dfs_heavy_edge(1, 1); 226 scanf("%d", &q); 227 char op; 228 for(int i = 0, a, b, c; i < q; ++i) { 229 scanf(" %c", &op); 230 if(op == 'Q') { 231 scanf("%d%d", &a, &b); 232 printf("%d\n", query(a, b)); 233 } else { 234 scanf("%d%d%d", &a, &b, &c); 235 modify(a, b, c); 236 } 237 } 238 } 239 } T; 240 241 int main() { 242 T.work(); 243 } View Code

?

轉載于:https://www.cnblogs.com/oyking/p/3897666.html

總結

以上是生活随笔為你收集整理的ACdream 1103 瑶瑶正式成为CEO（树链剖分+费用流）的全部內容，希望文章能夠幫你解決所遇到的問題。

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