#include #include using namespace std; const int MAXV = 200; class edge { public: int dest; edge * next; edge(int d, edge* n = 0) : dest(d), next(n) {} }; class vertex { public: string name; long long nsquawk; edge* adj; vertex(string n="") { name = n; nsquawk = 0; adj = new edge(-1); // dummy header } void addEdge(int w) { adj->next = new edge(w, adj->next); } }; class graph { public: vertex *vlist; int nvert; graph(int nv=10) { nvert = 0; vlist = new vertex[nv]; } void clear() { if (vlist != 0) delete [] vlist; } void addVertex(string n) { vlist[nvert++].name = n; } int getVertexNum(string n) { for(int i=0; inext; p != 0; p = p edge *p = vlist[v].adj; while (p->next != 0) { if (p->next->dest == w) break; p = p->next; } if (p->next == 0) { cout << "ERROR: vertex " << w << " not adjacent to vertex " << v << endl; return; } edge* tmp = p->next; p->next = tmp->next; delete tmp; } bool findPath(int curr, int dest, int& len, int path[], bool visited[]) { path[len++] = curr; if (curr == dest) { return true; } for(edge* p = vlist[curr].adj->next; p != 0; p = p->next) { if (!visited[p->dest]) { visited[p->dest] = true; if (findPath(p->dest, dest, len, path, visited)) return true; len--; } } return false; } bool findPath(int path[], int& len) { bool visited[nvert]; for(int i=0; inext; p != 0; p = p->next) out << ' ' << vlist[p->dest].name; out << endl; } } }; ostream& operator<<(ostream& out, graph g) { g.print(out); return out; } int main() { int ntot, ns, nf, nt; string name; cin >> ntot >> ns >> nf >> nt; graph g(2+ntot+2*nt); g.addVertex("source"); g.addVertex("sink"); for(int i=0; i> name; g.addEdge("source", name); } for(int i=0; i> name; g.addEdge(name, "sink"); } for(int i=0; i> n; for(int j=0; j> name; int v = g.getVertexNum(name); if (v < 2+ns) // raw material state g.addEdge(v, 2+ns+nf+2*i); else if (v < 2+ns+nf) // factory state g.addEdge(2+ns+nf+2*i+1, v); else { // other state g.addEdge(v, 2+ns+nf+2*i); g.addEdge(2+ns+nf+2*i+1, v); } } } //cout << g << endl; int *path = new int[g.nvert]; int len; int count=0; while (g.findPath(path, len)) { count++; for(int i=1; i