#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; static const double EPS = 1e-8; static const double PI = 4.0 * atan(1.0); static const double PI2 = 8.0 * atan(1.0); typedef long long ll; // Spaghetti Source - グラフの基本要素 // http://www.prefield.com/algorithm/graph/graph.html struct Edge { int src; int dst; int weight; int flow; Edge(int s, int d, int w, int f) : src(s), dst(d), weight(w), flow(f) {} }; bool operator < (const Edge &e, const Edge &f) { return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!! e.src != f.src ? e.src < f.src : e.dst < f.dst; } typedef list Edges; typedef vector Graph; // Spaghetti Source - 単一始点最短路 (Bellman Ford) // http://www.prefield.com/algorithm/graph/bellman_ford.html static const int INF = INT_MAX / 2; static const int NEGATIVE_CYCLE = INT_MIN / 2; bool bellmanFord(const Graph& g, int s, vector& dist, vector& prev) { const int n = g.size(); dist.assign(n, INF); dist[s] = 0; prev.assign(n, -2); for (int k = 0; k < n; ++k) { for (int i = 0; i < n; ++i) { for (list::const_iterator e = g[i].begin(); e != g[i].end(); ++e) { if (dist[e->dst] > dist[e->src] + e->weight) { dist[e->dst] = dist[e->src] + e->weight; prev[e->dst] = e->src; if (k == n - 1) { dist[e->dst] = NEGATIVE_CYCLE; return false; } } } } } return true; } vector buildPath(const vector &prev, int t) { vector memo(prev.size(), false); vector path; for (int u = t; u >= 0 ; u = prev[u]) { if (memo[u]) { path.erase(path.begin(), find(path.begin(), path.end(), u)); path.push_back(u); break; } memo[u] = true; path.push_back(u); } reverse(path.begin(), path.end()); return path; } void updatePath(Graph& g, const vector& path, int& restFlow, int& totalWeight, int& totalFlow) { int bestFlow = restFlow; for (int i = 0; i < (int)path.size() - 1; ++i) { // 一番コストの低い枝で更新する const int from = path[i]; const int to = path[i + 1]; int bestWeight = INT_MAX; int localBestFlow = 0; for (Edges::iterator it = g[from].begin(); it != g[from].end(); ++it) { if (it->src == from && it->dst == to && bestWeight > it->weight) { bestWeight = it->weight; localBestFlow = it->flow; } } if (bestFlow > localBestFlow) { bestFlow = localBestFlow; } } restFlow -= bestFlow; for (int i = 0; i < (int)path.size() - 1; ++i) { const int from = path[i]; const int to = path[i + 1]; int bestWeight = INT_MAX; list::iterator edge = g[from].end(); for (list::iterator it = g[from].begin(); it != g[from].end(); ++it) { if (it->src == from && it->dst == to && bestWeight > it->weight) { bestWeight = it->weight; edge = it; } } assert(edge != g[from].end()); edge->flow -= bestFlow; if (edge->flow == 0) { g[from].erase(edge); } edge = g[to].end(); for (list::iterator it = g[to].begin(); it != g[to].end(); ++it) { if (it->src == to && it->dst == from && it->weight == -bestWeight) { edge = it; break; } } if (edge == g[to].end()) { g[to].push_back(Edge(to, from, -bestWeight, bestFlow)); } else { edge->flow += bestFlow; } totalWeight += bestFlow * bestWeight; } if (path.front() != path.back()) { totalFlow += bestFlow; } } // <費用, フロー> pair minimumCostFlow(Graph &g, int s, int t, int restFlow) { int totalWeight = 0; int totalFlow = 0; const int n = g.size(); for (;;) { //ステップ0:人工問題を解いて、需要供給量を満たすフローを求める //ステップ1:現在のフローに関する残余ネットワークを作る vector label(n, -2); label[s] = -1; bool updated = true; while (updated) { updated = false; for (Graph::iterator it = g.begin(); it != g.end(); ++it) { for (Edges::iterator jt = it->begin(); jt != it->end(); ++jt) { if (label[jt->src] != -2 && label[jt->dst] == -2) { label[jt->dst] = jt->src; updated = true; } } } } if (label[t] == -2 || restFlow == 0) { //ステップ2:残余ネットワークに費用が負の閉路が存在しない⇒ 現在のフローは費用最小(終了) vector dist; vector prev; bellmanFord(g, s, dist, prev); if (find(dist.begin(), dist.end(), NEGATIVE_CYCLE) == dist.end()) { break; } //ステップ3:残余ネットワークの費用が負の閉路を求め、それを用いて現在のフローを更新する int cycleStart = (int)distance(dist.begin(), find(dist.begin(), dist.end(), NEGATIVE_CYCLE)); vector path = buildPath(prev, cycleStart); int tempRestFlow = INT_MAX; updatePath(g, path, tempRestFlow, totalWeight, totalFlow); //ステップ4:ステップ1へ戻る } else { vector path; int current = t; while (current != -1) { path.push_back(current); current = label[current]; } reverse(path.begin(), path.end()); updatePath(g, path, restFlow, totalWeight, totalFlow); } } return make_pair(totalWeight, totalFlow); } struct Train { int direction; int departure; int arrival; int numberOfCars; }; int main() { int U, D; cin >> U >> D; map timeA; map timeB; vector input; for (int i = 0; i < U; ++i) { Train t; t.direction = 0; cin >> t.numberOfCars >> t.departure >> t.arrival; input.push_back(t); timeA.insert(make_pair(t.departure, 0)); timeB.insert(make_pair(t.arrival, 0)); } for (int i = 0; i < D; ++i) { Train t; t.direction = 1; cin >> t.numberOfCars >> t.departure >> t.arrival; input.push_back(t); timeA.insert(make_pair(t.arrival, 0)); timeB.insert(make_pair(t.departure, 0)); } int nodeIndex = 0; for (map::iterator it = timeA.begin(); it != timeA.end(); ++it) { it->second = nodeIndex++; } for (map::iterator it = timeB.begin(); it != timeB.end(); ++it) { it->second = nodeIndex++; } const int numberOfNodes = nodeIndex; Graph g(numberOfNodes); for (int i = 0; i < (int)timeA.size() - 1; ++i) { g[i].push_back(Edge(i, i + 1, 0, INT_MAX / 2)); } for (int i = timeA.size(); i < (int)timeA.size() + (int)timeB.size() - 1; ++i) { g[i].push_back(Edge(i, i + 1, 0, INT_MAX / 2)); } for (vector::iterator it = input.begin(); it != input.end(); ++it) { if (it->direction == 0) { const int from = timeA[it->departure]; const int to = timeB[it->arrival]; g[from].push_back(Edge(from, to, -1, it->numberOfCars)); } else { const int from = timeB[it->departure]; const int to = timeA[it->arrival]; g[from].push_back(Edge(from, to, 0, it->numberOfCars)); } } const int answer = -minimumCostFlow(g, 0, timeA.size() + timeB.size() - 1, 1).first; cout << answer << endl; }