Grafalgo
Library of useful data structures and algorithms
|
00001 00014 #include "stdinc.h" 00015 #include "Mflograph.h" 00016 #include "List.h" 00017 00018 using namespace grafalgo; 00019 00020 main() { 00021 vertex u,v; edge e; int sum; 00022 Mflograph fg; fg.read(cin); 00023 00024 // verify that capacity constraints and min flow requirements 00025 // are respected 00026 for (e = fg.first(); e != 0; e = fg.next(e)) { 00027 u = fg.tail(e); v = fg.head(e); string s; 00028 if (fg.f(u,e) < 0) 00029 cout << "Negative flow on edge " 00030 << e << "=" << fg.edge2string(e,s) << endl; 00031 if (fg.f(u,e) > fg.cap(u,e)) 00032 cout << "Flow exceeds capacity on edge " 00033 << e << "=" << fg.edge2string(e,s) << endl; 00034 if (fg.f(u,e) < fg.minFlo(e)) 00035 cout << "Flow less than min flow requirement on edge " 00036 << e << "=" << fg.edge2string(e,s) << endl; 00037 } 00038 00039 // verify that flow at each node is balanced 00040 for (u = 1; u <= fg.n(); u++) { 00041 if (u == fg.src() || u == fg.snk()) continue; 00042 sum = 0; 00043 for (e = fg.firstAt(u); e != 0; e = fg.nextAt(u,e)) { 00044 sum -= fg.f(u,e); 00045 } 00046 if (sum != 0) cout << "Vertex " << u << " is not balanced\n"; 00047 } 00048 00049 // Verify that the flow is maximum by computing hop-count distance 00050 // over all edges that are not saturated. If sink ends up with a 00051 // distance smaller than n, then there is a path to sink with 00052 // non-zero residual capacity. 00053 int *d = new int[fg.n()+1]; 00054 for (u = 1; u <= fg.n(); u++) d[u] = fg.n(); 00055 d[fg.src()] = 0; 00056 List q(fg.n()); q.addLast(fg.src()); 00057 while (!q.empty()) { 00058 u = q.first(); q.removeFirst(); 00059 for (e = fg.firstAt(u); e != 0; e = fg.nextAt(u,e)) { 00060 v = fg.mate(u,e); 00061 if (fg.res(u,e) > 0 && d[v] > d[u] + 1) { 00062 d[v] = d[u] + 1; q.addLast(v); 00063 } 00064 } 00065 } 00066 if (d[fg.snk()] < fg.n()) printf("Not a maximum flow\n"); 00067 }