首页 > 代码库 > HDU 5029 Relief grain（离线+线段树+启发式合并）（2014 ACM/ICPC Asia Regional Guangzhou Online）
HDU 5029 Relief grain（离线+线段树+启发式合并）（2014 ACM/ICPC Asia Regional Guangzhou Online）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5029
Problem Description
The soil is cracking up because of the drought and the rabbit kingdom is facing a serious famine. The RRC(Rabbit Red Cross) organizes the distribution of relief grain in the disaster area.
We can regard the kingdom as a tree with n nodes and each node stands for a village. The distribution of the relief grain is divided into m phases. For each phases, the RRC will choose a path of the tree and distribute some relief grain of a certain type for every village located in the path.
There are many types of grains. The RRC wants to figure out which type of grain is distributed the most times in every village.
We can regard the kingdom as a tree with n nodes and each node stands for a village. The distribution of the relief grain is divided into m phases. For each phases, the RRC will choose a path of the tree and distribute some relief grain of a certain type for every village located in the path.
There are many types of grains. The RRC wants to figure out which type of grain is distributed the most times in every village.
Input
The input consists of at most 25 test cases.
For each test case, the first line contains two integer n and m indicating the number of villages and the number of phases.
The following n-1 lines describe the tree. Each of the lines contains two integer x and y indicating that there is an edge between the x-th village and the y-th village.
The following m lines describe the phases. Each line contains three integer x, y and z indicating that there is a distribution in the path from x-th village to y-th village with grain of type z. (1 <= n <= 100000, 0 <= m <= 100000, 1 <= x <= n, 1 <= y <= n, 1 <= z <= 100000)
The input ends by n = 0 and m = 0.
For each test case, the first line contains two integer n and m indicating the number of villages and the number of phases.
The following n-1 lines describe the tree. Each of the lines contains two integer x and y indicating that there is an edge between the x-th village and the y-th village.
The following m lines describe the phases. Each line contains three integer x, y and z indicating that there is a distribution in the path from x-th village to y-th village with grain of type z. (1 <= n <= 100000, 0 <= m <= 100000, 1 <= x <= n, 1 <= y <= n, 1 <= z <= 100000)
The input ends by n = 0 and m = 0.
Output
For each test case, output n integers. The i-th integer denotes the type that is distributed the most times in the i-th village. If there are multiple types which have the same times of distribution, output the minimal one. If there is no relief grain in a village, just output 0.
题目大意：有一棵n个点的数，有m个操作，每次给路径path(x, y)分配一个值z。最后问每个点被分配次数最多的值，如有多个输出最小的一个。
思路：暂无。
代码（3046MS）：
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 #include <vector> 6 using namespace std; 7 typedef pair<int, int> PII; 8 9 const int MAXV = 100010; 10 const int MAXE = MAXV << 1; 11 const int MAXT = MAXV << 2; 12 13 int head[MAXV], ecnt; 14 int to[MAXE], next[MAXE]; 15 int n, m, maxz; 16 17 void init() { 18 memset(head + 1, -1, n * sizeof(int)); 19 ecnt = 0; 20 } 21 22 void add_edge(int u, int v) { 23 to[ecnt] = v; next[ecnt] = head[u]; head[u] = ecnt++; 24 to[ecnt] = u; next[ecnt] = head[v]; head[v] = ecnt++; 25 } 26 27 #define mid ((l + r) >> 1) 28 struct Node { 29 Node *lson, *rson; 30 int val, cnt, size; 31 Node() { 32 val = cnt = size = 0; 33 } 34 void update() { 35 Node *s = lson->cnt >= rson->cnt ? lson : rson; 36 val = s->val; 37 cnt = s->cnt; 38 size = lson->size + rson->size; 39 } 40 } *nil; 41 Node statePool[MAXT * 3]; 42 Node *stk[MAXT * 3]; 43 int top, scnt; 44 45 Node* new_node() { 46 Node *p; 47 if(top) p = stk[--top]; 48 else p = &statePool[scnt++]; 49 p->lson = p->rson = nil; 50 p->val = p->cnt = p->size = 0; 51 return p; 52 } 53 54 void del_node(Node *p) { 55 stk[top++] = p; 56 } 57 58 void remove(Node *y) { 59 if(y->lson != nil) remove(y->lson); 60 if(y->rson != nil) remove(y->rson); 61 del_node(y); 62 } 63 64 void modify(Node *&x, int l, int r, int pos, int val) { 65 if(x == nil) x = new_node(); 66 if(l == r) { 67 x->val = l; 68 x->cnt += val; 69 x->size = (x->cnt > 0); 70 } else { 71 if(pos <= mid) modify(x->lson, l, mid, pos, val); 72 if(mid < pos) modify(x->rson, mid + 1, r, pos, val); 73 x->update(); 74 } 75 } 76 77 void merge(Node *x, Node *y, int l, int r) { 78 if(y->size != 0) { 79 if(l == r) { 80 modify(x, 1, maxz, l, y->cnt); 81 } else { 82 merge(x, y->lson, l, mid); 83 merge(x, y->rson, mid + 1, r); 84 } 85 } 86 } 87 88 Node* merge(Node *x, Node *y) { 89 if(x->size < y->size) swap(x, y); 90 merge(x, y, 1, maxz); 91 remove(y); 92 return x; 93 } 94 95 vector<PII> query[MAXV]; 96 struct Modify { 97 int u, v, c, lca; 98 void read(int i) { 99 scanf("%d%d%d", &u, &v, &c);100 maxz = max(maxz, c);101 query[u].push_back(make_pair(v, i));102 query[v].push_back(make_pair(u, i));103 }104 } ask[MAXV];105 int fa[MAXV];106 bool vis[MAXV];107 108 int find_set(int x) {109 return fa[x] == x ? x : fa[x] = find_set(fa[x]);110 }111 112 void lca(int u, int f) {113 for(int p = head[u]; ~p; p = next[p]) {114 int &v = to[p];115 if(v == f || vis[v]) continue;116 lca(v, u);117 fa[v] = u;118 }119 vis[u] = true;120 for(vector<PII>::iterator it = query[u].begin(); it != query[u].end(); ++it) {121 if(vis[it->first]) {122 ask[it->second].lca = find_set(it->first);123 }124 }125 }126 127 vector<PII> pre[MAXV], nxt[MAXV];128 int ans[MAXV];129 130 Node* dfs(int u, int f) {131 Node *x = new_node();132 for(int p = head[u]; ~p; p = next[p]) {133 int v = to[p];134 if(v == f) continue;135 x = merge(x, dfs(v, u));136 }137 for(vector<PII>::iterator it = pre[u].begin(); it != pre[u].end(); ++it)138 modify(x, 1, maxz, it->first, it->second);139 ans[u] = x->val;140 for(vector<PII>::iterator it = nxt[u].begin(); it != nxt[u].end(); ++it)141 modify(x, 1, maxz, it->first, it->second);142 return x;143 }144 145 void solve() {146 for(int i = 1; i <= n; ++i) {147 fa[i] = i;148 vis[i] = false;149 pre[i].clear(); nxt[i].clear();150 }151 lca(1, 0);152 for(int i = 0; i < m; ++i) {153 const Modify &t = ask[i];154 pre[t.u].push_back(make_pair(t.c, 1));155 pre[t.v].push_back(make_pair(t.c, 1));156 pre[t.lca].push_back(make_pair(t.c, -1));157 nxt[t.lca].push_back(make_pair(t.c, -1));158 }159 top = scnt = 0;160 Node *p = dfs(1, 0);161 if(p != nil) remove(p);162 163 for(int i = 1; i <= n; ++i)164 printf("%d\n", ans[i]);165 }166 167 int main() {168 nil = new Node();169 nil->lson = nil->rson = nil;170 171 while(scanf("%d%d", &n, &m) != EOF) {172 if(n == 0 && m == 0) break;173 init();174 for(int i = 1, u, v; i < n; ++i) {175 scanf("%d%d", &u, &v);176 add_edge(u, v);177 }178 for(int i = 1; i <= n; ++i) query[i].clear();179 maxz = 0;180 for(int i = 0; i < m; ++i) ask[i].read(i);181 solve();182 }183 }
HDU 5029 Relief grain（离线+线段树+启发式合并）（2014 ACM/ICPC Asia Regional Guangzhou Online）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。