#include<iostream> #include<vector> #include<list> #include<string> using namespace std; class edge; class node { public : int cost; vector<edge* > edges; edge* from; string name; bool onq; node() { cost = 100; = null; onq = false; } ~node() { vector<edge *>().swap(edges); delete from; } void clear() { cost = 0; vector<edge *>().swap(edges); = null; } }; class edge { public: node* destination; int capacity; int cost; edge* dual; edge() { } ~edge() { vector<edge*>().swap(destination->edges); delete destination; delete dual; destination = null; dual = null; } edge(node* n, int c, int s) { capacity = c; cost = s; destination = n; dual = null; } }; int mcmf(node* src, node* snk, vector<node*> &nodes) { int result = 0; list<node* > queue; while(true) { for(int = 0 ; < nodes.size() ; ++i) { nodes.at(i)->cost = 100; nodes.at(i)->from = null; } src->cost = 0; queue.clear(); queue.push_back(src); src->onq = true; int count = 0; while(!queue.empty()) { node* node = queue.front(); queue.pop_front(); node->onq = false; for(int = 0 ; < node->edges.size() ; ++i) { edge* edge = node->edges[i]; if(edge->capacity > 0 && node->cost + edge->cost < edge->destination->cost) { edge->destination->cost = node->cost + edge->cost; edge->destination->from = edge; if(!edge->destination->onq) { edge->destination->onq = true; queue.push_back(edge->destination); } } } } if(snk->from == null) break; int min = 0x7fffffff; for(node* node = snk ; node->from != null ; ) { edge* edge = node->from; if(edge->capacity < min) min = edge->capacity; node = edge->dual->destination; } for(node* node = snk ; node->from != null ;) { edge* edge = node->from; edge->capacity -= min; edge->dual->capacity += min; node = edge->dual->destination; } result += snk->cost; for(list<node*>::iterator iter = queue.begin() ; iter != queue.end() ; ++iter) delete (*iter); queue.clear(); } return result; } void link(node *node1, node *node2, int capacity, int cost) { edge* e1 = new edge(node2, capacity, cost); edge* e2 = new edge(node1, 0, -cost); e1->dual = e2; e2->dual = e1; node1->edges.push_back(e1); node2->edges.push_back(e2); } int main() { int n, m; vector<node* > nodes; while(cin >> n >> m) { if(n == 0 && m == 0) break; nodes.clear(); node* source = new node(); nodes.push_back(source); node* sink = new node(); nodes.push_back(sink); vector<vector<node* > > position(n); for(int = 0 ; < n ; ++i) { int p; cin >> p; position[i] = vector<node*>(p); for(int j = 0 ; j < p ; ++j) { node* node = new node; position[i][j] = node; nodes.push_back(node); link(node, sink, 1, 0); } } for(int = 0 ; < m ; ++i) { node* student = new node(); nodes.push_back(student); link(source, student, 1, 0); int year, cost; cin >> year; cost = 13 - year*4; for(int j = 0 ; j < 4 ; ++j) { int pre; cin >> pre; for(int k = 0 ; k < position[pre].size() ; ++k) { link(student, position[pre][k], 1, cost+j); } } } cout << 13*m-mcmf(source, sink, nodes) << endl; delete source; delete sink; for(vector<vector<node*> >::iterator iter1 = position.begin() ; iter1 != position.end() ; ++ iter1) for(vector<node*>::iterator iter2 = (*iter1).begin(); iter2 != (*iter1).end() ; ++iter2) delete (*iter2); vector<vector<node *> >().swap(position); vector<node*>().swap(nodes); } } this whole code
this code created mcmf graph algorithm
i submit code algorithm site fail because memory excess
this code has more 128mb....
i think not free memory allocated in link function
i try catch memory leak in visual studio many log appeared can't think solution
im sorry code's length
can find solution allocation
thank you
these questions next impossible answer because no 1 knows going on in online judge, here's hum-dinger of memory leak fix:
class nodes destructor,
~node() { vector<edge *>().swap(edges); delete from; } deletes edge before edge's destructor has been defined. uncool, because program can't call edge destructor free whatever resources edge owns. , looks ~edge far trivial:
~edge() { vector<edge*>().swap(destination->edges); delete destination; delete dual; destination = null; dual = null; } none of code ever run. way, setting destination , dual null wasted effort. edge gone in few clock cycles, no 1 ever care.
also, vector<edge*>().swap(destination->edges); doesn't want do. it's not freeing of edges. it's moving pointers temporary that's go out of scope , lose edge pointers forever.
solution:
move ~node after definition of ~edge
class node { ... ~node(); // declare ... }; class edge { ... }; node::~node() { vector<edge *>().swap(edges); delete from; } and above vector<edge *>().swap(edges); isn't doing of use you. suspect after more this:
node::~node() { (edge * edge: edges) { delete edge; } delete from; } and recommend thinking hard doing from.
on second thought, rethink how doing this. deleting edge::destination bad idea because, unless 1 directional tree, given node destination of edge. deleteing more once not idea. having same node represented more 1 object bad idea.
