题面

有 $n$ 个变量 $w[1]\sim w[n]$ ，每个变量的值为 $W$ 或 $-W$ 。

有 $p$ 个公式 $f(i)=a_i|w[x_i]-w[y_i]|+b_i|w[y_i]-w[z_i]|+c_i|w[z_i]-w[x_i]|+d_i(w[x_i]-w[y_i])+e_i(w[y_i]-w[z_i])+f_i(w[z_i]-w[x_i])$ 。 其中 $|x|$ 表示 $x$ 的绝对值

有 $q$ 个要求，形如 $w[x]\leq w[y]$ 或 $w[x]=w[y]$ 或 $w[x]\lt w[y]$ 。

你希望知道 $\sum w[i]+\sum f(i)$ 的最小值。

$T\leq 10,n\leq 500,p,q\leq 1000,1\leq W\leq 10^6,0\leq a_i,b_i,c_i,d_i,e_i,f_i\leq 1000$

题解

这种变量的带各种限制的题一般可以转化到图论。这种就是最小割模型。

每个变量一个点。发现每个变量的值为 $W$ 或 $-W$ ，其实建边的时候可以设为 1，最后再乘 $W$ 。就从源点连向 $i$ 流量为 $1$ 的， $i$ 连向汇点流量为 $-1$ 的。如此，选哪个就割哪条边。

对于要求，

1. $w[x]\leq w[y]$ ，即排除了 $y$ 选 $-1$ 但 $x$ 选 $1$ 的情况，那么建一条 $(y\rightarrow x,\infty)$ 的边，阻挡了这个情况；
2. $w[x]= w[y]$ 两遍 1 操作；
3. $w[x]<w[y]$ ，就是规定了 $w[x]=-1,w[y]=1$ ，那么把 $(S\rightarrow x)$ 改为 $\infty$ ， $y$ 同理。

对于公式，

1. $a_i|w[x_i]-w[y_i]|+b_i|w[y_i]-w[z_i]|+c_i|w[z_i]-w[x_i]|$ ，同号则无，异号则 $2\times a/b/c$ ，给该边加上这个值即可。
2. $d_i(w[x_i]-w[y_i])+e_i(w[y_i]-w[z_i])+f_i(w[z_i]-w[x_i])$ ，就是 $x,y,z$ 分别有多少额外点权。

代码

const int N = 610, M = (N + 8000) << 1;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n, p, q; ll W;
	struct NetworkFlow {
		const int inf = 707406378;
		int S, T;
		int head[N], tot = 1;
		struct Edge {
			int to; ll w; int op, nxt;
		} e[M << 1];
		void add_edge(int u, int v, ll w) {
			e[++tot] = (Edge) {v, w, tot ^ 1, head[u]}, head[u] = tot;
			e[++tot] = (Edge) {u, 0, tot ^ 1, head[v]}, head[v] = tot;
		}
		NetworkFlow() {tot = 1;}

		void init (int _S, int _T) { S = _S, T = _T, tot = 1; memset (head, 0, sizeof head); }
		int dis[N];
		queue <int> q;
		bool bfs() {
			while (!q.empty()) q.pop();
			memset (dis, 127 / 3, sizeof dis);
			dis[S] = 0;
			q.push(S);
			while (!q.empty()) {
				int u = q.front(); q.pop();
				for (int i = head[u]; i; i = e[i].nxt) {
					int v = e[i].to;
					if (dis[v] > dis[u] + 1 && e[i].w) {
						dis[v] = dis[u] + 1;
						if (v == T) return 1;
						q.push(v);
					}
				}
			}
			return 0;
		}
		ll dfs (int u, ll flow) {
			if (u == T) return flow;
			ll sum = 0;
			for (int i = head[u]; i; i = e[i].nxt) {
				int v = e[i].to;
				if (dis[v] == dis[u] + 1 && e[i].w) {
					ll f = dfs(v, min(e[i].w, flow - sum));
					if (!f) dis[v] = -1;
					e[i].w -= f;
					e[e[i].op].w += f;
					sum += f;
					if (sum == flow) break;
				}
			}
			return sum;
		}
		ll dinic () { ll ret = 0; for (; bfs(); ret += dfs(S, inf)); return ret; }
	} nf;
	bool infy[2][N];
	ll per[N], E[N][N];
	int main () {
		for (int T = Read(); T--; ) {
			memset (infy, 0, sizeof infy);
			memset (per, 0, sizeof per);
			memset (E, 0, sizeof E);
			n = Read(), W = Read(), p = Read(), q = Read();
			nf.init(n + 1, n + 2);
			for (int i = 1; i <= p; i++) {
				int x = Read(), y = Read(), z = Read();
				int a = Read(), b = Read(), c = Read();
#define ed(x, y, a) E[(x)][(y)] += 2 * a, E[(y)][(x)] += 2 * a
				ed(x, y, a); ed(y, z, b); ed(z, x, c);
#undef ed
				int d = Read(), e = Read(), f = Read();
				per[x] += d - f, per[y] += e - d, per[z] += f - e;
			}
			for (int i = 1; i <= q; i++) {
				int x = Read(), y = Read(), r = Read();
				switch (r) {
					case 0: E[y][x] = nf.inf; break;
					case 2: infy[0][x] = 1, infy[1][y] = 1; break;
					default: E[x][y] = E[y][x] = nf.inf;
				}
			}
			for (int i = 1; i <= n; i++)
				for (int j = 1; j <= n; j++) E[i][j] && (nf.add_edge(i, j, E[i][j]), 1);
			for (int i = 1; i <= n; i++) 
				nf.add_edge(nf.S, i, infy[0][i]? nf.inf: (per[i] + 1)), 
					nf.add_edge(i, nf.T, infy[1][i]? nf.inf: -(per[i] + 1));
			printf ("%lld\n", nf.dinic() * W);
		}
		return 0;
	}
}

int main () {
	string str = "variable";
	freopen((str + ".in").c_str(), "r", stdin);
	freopen((str + ".out").c_str(), "w", stdout);
	Main::main();
	return 0;
}