#include <cstdio> #include <algorithm> #include <vector> #include <unordered_set> using namespace std; struct Reaction{ int target, priority; bool operator<(const Reaction& lhs) const{ //if(priority != lhs.priority) return priority < lhs.priority; //return target < lhs.target; } }; int flaskCount, seqLen, pairCount; long long result; void processPair(const pair<int, int>& seq, vector<Reaction>* reactions, unordered_set<int>* content, int* flaskCap, pair<int, int>* reactionList){ int source = seq.first; int target = seq.second; unordered_set<int>& lhsContent = content[source]; unordered_set<int>& rhsContent = content[target]; vector<int> reQueue; for(int lhs: lhsContent){ for(const Reaction& rc: reactions[lhs]){ auto it = rhsContent.find(rc.target); if(it!=rhsContent.end()) reQueue.push_back(rc.priority); } } rhsContent.insert(lhsContent.begin(), lhsContent.end()); lhsContent.clear(); sort(reQueue.begin(), reQueue.end()); for(const int rec : reQueue){ int r1 = reactionList[rec].first; int r2 = reactionList[rec].second; int recValue = min(flaskCap[r1], flaskCap[r2]); result += recValue*2; flaskCap[r1] -= recValue; flaskCap[r2] -= recValue; if(flaskCap[r1] == 0) rhsContent.erase(r1); if(flaskCap[r2] == 0) rhsContent.erase(r2); } } int main(){ result = 0; scanf("%d%d%d", &flaskCount, &seqLen, &pairCount); unordered_set<int>* flaskContent = new unordered_set<int>[flaskCount]; //capacities int* flaskCap = new int[flaskCount]; for(int i=0; i<flaskCount; i++){ scanf("%d", &flaskCap[i]); flaskContent[i].insert(i); } //sequence pair<int, int>* seq = new pair<int,int>[seqLen]; for(int i=0; i<seqLen; i++){ scanf("%d %d", &seq[i].first, &seq[i].second); seq[i].first--; seq[i].second--; } //reactions pair<int, int>* reactionPairs = new pair<int,int>[pairCount]; vector<Reaction>* reactions = new vector<Reaction>[flaskCount]; for(int i=0; i<pairCount; i++){ int s1, s2; scanf("%d%d", &s1, &s2); s1--; s2--; reactionPairs[i] = make_pair(s1,s2); Reaction r1, r2; r1.target = s2; r2.target = s1; r1.priority = r2.priority = i; reactions[s1].push_back(r1); reactions[s2].push_back(r2); } for(int i=0; i<seqLen; i++){ processPair(seq[i], reactions, flaskContent, flaskCap, reactionPairs); } printf("%lld\n", result); // delete []flaskContent; // delete []flaskCap; // delete []seq; // delete []reactionPairs; // delete []reactions; return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 | #include <cstdio> #include <algorithm> #include <vector> #include <unordered_set> using namespace std; struct Reaction{ int target, priority; bool operator<(const Reaction& lhs) const{ //if(priority != lhs.priority) return priority < lhs.priority; //return target < lhs.target; } }; int flaskCount, seqLen, pairCount; long long result; void processPair(const pair<int, int>& seq, vector<Reaction>* reactions, unordered_set<int>* content, int* flaskCap, pair<int, int>* reactionList){ int source = seq.first; int target = seq.second; unordered_set<int>& lhsContent = content[source]; unordered_set<int>& rhsContent = content[target]; vector<int> reQueue; for(int lhs: lhsContent){ for(const Reaction& rc: reactions[lhs]){ auto it = rhsContent.find(rc.target); if(it!=rhsContent.end()) reQueue.push_back(rc.priority); } } rhsContent.insert(lhsContent.begin(), lhsContent.end()); lhsContent.clear(); sort(reQueue.begin(), reQueue.end()); for(const int rec : reQueue){ int r1 = reactionList[rec].first; int r2 = reactionList[rec].second; int recValue = min(flaskCap[r1], flaskCap[r2]); result += recValue*2; flaskCap[r1] -= recValue; flaskCap[r2] -= recValue; if(flaskCap[r1] == 0) rhsContent.erase(r1); if(flaskCap[r2] == 0) rhsContent.erase(r2); } } int main(){ result = 0; scanf("%d%d%d", &flaskCount, &seqLen, &pairCount); unordered_set<int>* flaskContent = new unordered_set<int>[flaskCount]; //capacities int* flaskCap = new int[flaskCount]; for(int i=0; i<flaskCount; i++){ scanf("%d", &flaskCap[i]); flaskContent[i].insert(i); } //sequence pair<int, int>* seq = new pair<int,int>[seqLen]; for(int i=0; i<seqLen; i++){ scanf("%d %d", &seq[i].first, &seq[i].second); seq[i].first--; seq[i].second--; } //reactions pair<int, int>* reactionPairs = new pair<int,int>[pairCount]; vector<Reaction>* reactions = new vector<Reaction>[flaskCount]; for(int i=0; i<pairCount; i++){ int s1, s2; scanf("%d%d", &s1, &s2); s1--; s2--; reactionPairs[i] = make_pair(s1,s2); Reaction r1, r2; r1.target = s2; r2.target = s1; r1.priority = r2.priority = i; reactions[s1].push_back(r1); reactions[s2].push_back(r2); } for(int i=0; i<seqLen; i++){ processPair(seq[i], reactions, flaskContent, flaskCap, reactionPairs); } printf("%lld\n", result); // delete []flaskContent; // delete []flaskCap; // delete []seq; // delete []reactionPairs; // delete []reactions; return 0; } |