Untitled
unknown
plain_text
a year ago
4.5 kB
4
Indexable
Never
#include<iostream> #include<vector> #include<string> #include<queue> #include<cstring> using namespace std; struct Node { int id; int par; vector<int>child; int dis; int level; int dsum; int quantity; }pool[10009]; int poolsize; void init(int N, int mParent[], int mDistance[], int mQuantity[]) { poolsize = N; pool[0].id = 0; pool[0].par = -1; pool[0].dis = -1; pool[0].quantity = mQuantity[0]; pool[0].child.clear(); pool[0].level = 1; pool[0].dsum = mQuantity[0]; for (int i = 1; i < poolsize; i++) { pool[i].id = i; pool[i].par = mParent[i]; pool[mParent[i]].child.push_back(i); pool[i].dis = mDistance[i]; pool[i].quantity = mQuantity[i]; pool[i].child.clear(); pool[i].dsum = mQuantity[i]; pool[i].level = pool[mParent[i]].level + 1; int parentId = mParent[i]; while (parentId != -1) { pool[parentId].dsum += mQuantity[i]; parentId = pool[parentId].par; } } } int carry(int mFrom, int mTo, int mQuantity) { int start = pool[mFrom].id; int end = pool[mTo].id; pool[start].quantity -= mQuantity; pool[end].quantity += mQuantity; int cost = 0; while (start != end) { if (pool[start].level > pool[end].level) { pool[start].dsum -= mQuantity; cost += pool[start].dis; start = pool[start].par; } else if (pool[start].level < pool[end].level) { pool[end].dsum += mQuantity; cost += pool[end].dis; end = pool[end].par; } else { pool[start].dsum -= mQuantity; cost += pool[start].dis; start = pool[start].par; pool[end].dsum += mQuantity; cost += pool[end].dis; end= pool[end].par; } } return cost* mQuantity; } int gather(int mID, int mQuantity) { int cost = 0; int vis[10009]; int quant = mQuantity; memset(vis, 0, sizeof(vis)); pool[mID].quantity += mQuantity; vis[mID] = 1; vector<pair<int, int>> pendingUpdate; //pair distance and id priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; for (int i = 0; i < pool[mID].child.size(); i++) { int childId = pool[mID].child[i]; int distance = pool[childId].dis; pq.push({ distance, childId }); vis[childId] = 1; } if (pool[mID].par != -1) { pq.push({ pool[mID].dis, pool[mID].par }); vis[pool[mID].par] = 1; } while (pq.empty() == false) { auto x = pq.top(); pq.pop(); int currentQuantity = pool[x.second].quantity; int currentDistance = x.first; int currentId = x.second; if (currentQuantity < mQuantity) { pool[currentId].quantity = 0; mQuantity -= currentQuantity; cost += currentQuantity * currentDistance; pendingUpdate.push_back({ currentId, -currentQuantity }); for (int i = 0; i < pool[currentId].child.size(); i++) { int childId = pool[currentId].child[i]; if (vis[childId] == 0) { vis[childId] = 1; pq.push({ currentDistance + pool[childId].dis, childId }); } } int parentId = pool[currentId].par; if (parentId != -1 && vis[parentId] == 0) { vis[parentId] = 1; pq.push({ currentDistance + pool[currentId].dis, parentId }); } } else { pool[currentId].quantity -= mQuantity; pendingUpdate.push_back({ currentId, -mQuantity }); cost += mQuantity * currentDistance; break; } } pendingUpdate.push_back({ mID, quant }); for (int i = 0; i < pendingUpdate.size(); i++) { int currentId = pendingUpdate[i].first; int distanceToBeModified = pendingUpdate[i].second; while (currentId != -1) { pool[currentId].dsum += distanceToBeModified; currentId = pool[currentId].par; } } return cost; } int sum(int mID) { return pool[mID].dsum;; }