Untitled
plain_text
a month ago
4.6 kB
2
Indexable
Never
//--------------- #include<unordered_map> #include<set> using namespace std; struct node{ int quantity; int priQuantity; int parent; int numChild; int dep; //do sau cua cay int kc; //distance tu node --> parent node set<int> child; }Node[10001]; int idX; //unordered_map<int, int> anhxa; //--------------------- void updateParent(int idP, int mQuantity){ Node[idP].quantity += mQuantity; while(Node[idP].parent != -1){ idP = Node[idP].parent; Node[idP].quantity += mQuantity; } } void init(int N, int mParent[], int mDistance[], int mQuantity[]){ //clear idX = 0; //anhxa.clear(); //add root Node[idX].child.clear(); int i = 0; Node[idX].parent = -1; Node[idX].quantity = mQuantity[i]; Node[idX].kc = -1; Node[idX].numChild = 0; Node[idX].dep = 0; Node[idX].priQuantity = mQuantity[i]; idX++; //add node for(i = 1; i < N; i++){ //add node int mP = mParent[i]; Node[idX].child.clear(); Node[idX].numChild = 0; Node[idX].parent = mP; Node[idX].quantity = mQuantity[i]; Node[idX].kc = mDistance[i]; Node[idX].dep = Node[mP].dep + 1; Node[idX].priQuantity = mQuantity[i]; //update parent Node[mP].numChild++; Node[mP].child.insert(idX); updateParent(Node[idX].parent, mQuantity[i]); idX++; } } int carry(int mFrom, int mTo, int mQuantity){ int result = 0; Node[mFrom].priQuantity -= mQuantity; Node[mTo].priQuantity += mQuantity; while(Node[mFrom].dep > Node[mTo].dep){ Node[mFrom].quantity -= mQuantity; result += Node[mFrom].kc; mFrom = Node[mFrom].parent; } while(Node[mFrom].dep < Node[mTo].dep){ Node[mTo].quantity += mQuantity; result += Node[mTo].kc; mTo = Node[mTo].parent; } // khi mFrom.dep == mTo.dep while(mFrom != mTo){ Node[mFrom].quantity -= mQuantity; Node[mTo].quantity += mQuantity; result += Node[mFrom].kc + Node[mTo].kc; mFrom = Node[mFrom].parent; mTo = Node[mTo].parent; } return result * mQuantity; } //------------------------ struct node1{ int kc; }dij[10001]; struct cmp{ bool operator () (int id1, int id2){ if(dij[id1].kc == dij[id2].kc){ return id1 < id2; } return dij[id1].kc < dij[id2].kc; } }; set<int, cmp> hangdoi; unordered_map<int, int> visit; int IDDich; int Dijecktra(int mQuantity){ int cost=0; int idC = *hangdoi.begin(); hangdoi.erase(hangdoi.begin()); visit[idC] = 1; //Duyet qua tat ca cac child for(auto i = Node[idC].child.begin(); i != Node[idC].child.end(); i++){ if(!visit[*i]){ dij[*i].kc = dij[idC].kc + Node[*i].kc; hangdoi.insert(*i); } } //Duyet cha cua no if(idC != 0){ int idP = Node[idC].parent; if(!visit[idP]){ dij[idP].kc = dij[idC].kc + Node[idC].kc; hangdoi.insert(idP); } } while(mQuantity){ //Push node dau hang doi int id = *hangdoi.begin(); //Delete o dau tien cua hang doi hangdoi.erase(hangdoi.begin()); //Danh dau la da tham visit[id] = 1; int numQuantity = mQuantity < Node[id].priQuantity ? mQuantity : Node[id].priQuantity; mQuantity -= numQuantity; cost += dij[id].kc * numQuantity; carry(id, IDDich, numQuantity); //Duyet qua tat ca cac child for(auto i = Node[id].child.begin(); i != Node[id].child.end(); i++){ if(!visit[*i]){ dij[*i].kc = dij[id].kc + Node[*i].kc; hangdoi.insert(*i); } } //Duyet cha cua no if(id != 0){ int idP = Node[id].parent; if(!visit[idP]){ dij[idP].kc = dij[id].kc + Node[id].kc; hangdoi.insert(idP); } } } return cost; } int gather(int mID, int mQuantity){ visit.clear(); hangdoi.clear(); IDDich = mID; //new node dij[mID].kc = 0; hangdoi.insert(mID); return Dijecktra(mQuantity); } int sum(int mID){ return Node[mID].quantity; }