首页 > 代码库 > ACdream 1103 瑶瑶正式成为CEO（树链剖分+费用流）
ACdream 1103 瑶瑶正式成为CEO（树链剖分+费用流）
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 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。