10319.cpp

10319.cpp

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define Ms 1003
typedef pair<int, int> pi;

int t;

struct MF {
	struct edge {
		int to, c, f[100], t;
		edge *d;
		edge(int to1 = -1, int c1 = 0, int t1 = 0) :to(to1), c(c1), t(t1), d(nullptr) {
			for (int i = 0; i < 100; i++)f[i] = 0;
		}
		int spare(int time) { return c - f[time]; }
		void addFlow(int f1,int time) {
			f[time] += f1;
			d->f[time] -= f1;
		}
	};

	int S = Ms-2, E = Ms - 1, mf = 0, n, g, s, m, r, a, b, c, d, p, T;
	vector<edge*>adj[Ms];

	void init() {
		for (int i = 0; i < Ms; i++)adj[i].clear();
		mf = 0;
	}

	void addEdge(int u, int v, int c, int t) {
		edge *e1 = new edge(v, c, t), *e2 = new edge(u, 0, t);
		e1->d = e2;
		e2->d = e1;
		adj[u].push_back(e1);
		adj[v].push_back(e2);
	}

	int solve() {
		for (int StartTime = 0; StartTime < s&&mf<=g; StartTime++) {
			while (1) {
				int pre[Ms],nowTime=0;
				for (int i = 0; i < Ms; i++)pre[i] = -1;
				edge* path[Ms] = { 0 };
				queue<pi> q;
				q.push({ S,StartTime });
				while (!q.empty()) {
					pi now = q.front();
					q.pop();
					for (edge *e : adj[now.first]) {
						int next = e->to, nxtTime = now.second + e->t;
						if (pre[next] == -1 && e->spare(now.second) > 0 && nxtTime <= s) {
							pre[next] = now.first;
							path[next] = e;
							q.push({ next,nxtTime });
							if (next == E) {
								nowTime = nxtTime;
								break;
							}
						}
					}
				}
				if (pre[E] == -1)break;
				int flow = 1e9, tmpT = nowTime;
				for (int i = E; i != S; i = pre[i]) {
					tmpT -= path[i]->t;
					flow = min(flow, path[i]->spare(tmpT));
				}
				for (int i = E; i != S; i = pre[i]) {
					nowTime -= path[i]->t;
					path[i]->addFlow(flow,nowTime);
				}
				mf += flow;
				if (mf > g)break;
			}
		}
		return mf > g ? g : mf;
	}

	void inp() {
		cin >> n >> a >> g >> s >> m;
		addEdge(S, a, g, 0);
		while (m--) {
			cin >> a;
			addEdge(a, E, Ms, 0);
		}
		cin >> r;
		while (r--) {
			cin >> a >> b >> c >> d;
			addEdge(a, b, c, d);
		}
		cout << solve() << '\n';
	}
};

int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> t;
	while (t--) {
		MF m;
		m.init();
		m.inp();
	}
}