Description
有n个变量w[1]~w[n]，每个变量可以取W或-W。
有p个式子，形如Hi=ai|w[xi]-w[yi]|+bi|w[yi]-w[zi]|+ci|w[zi]-w[xi]|+di(w[xi]-w[yi])+ei(w[yi]-w[zi])+fi(w[zi]-w[xi])。
有q个条件，形如w[x]<=w[y]或w[x]=w[y]或w[x]<w[y]。
最小化sigma(wi)+sigma(Hi)。
Data Constraint
数据组数≤10，n≤500, p,q≤1000, W≤10^6, 系数≤10^3，所有数字∈N。
Solution
奇怪的条件限制+不大的数据范围=网络流。
第一次做最小割+二元关系的题目。
考虑建图，首先对于每个变量w，连正权边S(s,i)和负权边S(i,t)，割啥选啥
然后是 H(i)，先考虑 x, y，取绝对值 = 异号2a 同号为0 ⟹ 连一条权值为2a的无向边(x, y)
后面的有点复杂，拆开式子后化为 (d - f) * w ⟹ 有向边(s, x) += (d - f) * w，无向边(x, t) -= (d - f) * w
再考虑限制条件，
w[x] ≤ w[y] ⟹ 有向边(y, x) = inf，表示要不然割(s, y)，要不然割(x, t)和(y, t)
w[x] = w[y] ⟹ 无向边(x, y) = inf，表示要不然同时割(s, x)(s, y)，要不然同时割(x, t)(y, t)
w[x] > w[y] ⟹ 有向边(s, x) = (y, t) = inf
这样子图就建好啦！
但是有负权边…………
所有(s, x), (x, t) += inf（一个极大值但别超过最大值，超过了会不会WA我也不造，注意这里指无向边）
其他的边都是inf边或补正边可以不加（为什么？）
最后答案减去 n * inf （共割了n条边）
最大流然后没啦！
Code
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 501
#define M 1000
#define ll long long
#define fo(i, x, y) for(int i = x; i <= y; i ++)
#define Mes(a, x) memset(a, x, sizeof a)
#define Min(x, y) (x < y ? x : y)
void read(ll &x) {
char ch = getchar(); x = 0;
while (ch < '0' || ch > '9') ch = getchar();
while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + ch - 48, ch = getchar();
}
const ll inf = (1ll << 40), INF = (1ll << 50);
int dis[N + 1], gap[N + 1], pre[N + 1], be[N + 1];
ll his[N + 1], f[N + 1][N + 1];
ll n, m, W, p, q;
ll Sap() {
Mes(dis, 0), Mes(gap, 0), Mes(be, 0);
gap[0] = m + 1;
ll sum = 0, aug = INF;
for (int u = 0, flow; dis[u] < m; ) {
his[u] = aug, flow = 0;
fo(i, be[u], m) if (f[u][i] > 0 && dis[u] - 1 == dis[i]) {
pre[i] = u;
aug = Min(aug, f[u][i]);
be[u] = i;
u = i;
flow = 1;
if (u == m) {
sum += aug;
while (u) {
f[u][pre[u]] += aug, f[pre[u]][u] -= aug;
u = pre[u];
}
aug = inf;
}
break;
}
if (flow) continue;
int v = 0;
fo(i, 0, m) if (f[u][i] > 0 && dis[i] < dis[v])
v = i;
if (-- gap[dis[u]] == 0) break;
++ gap[ dis[u] = dis[v] + 1 ];
be[u] = v;
if (u) u = pre[u], aug = his[u];
}
return sum;
}
int main() {
freopen("variable1.in", "r", stdin);
freopen("variable.out", "w", stdout);
ll T; read(T);
while (T --) {
Mes(f, 0);
read(n), read(W), read(p), read(q);
m = n + 1;
ll x, y, z, a, b, c, d, e, f1;
fo(i, 1, p) {
read(x), read(y), read(z), read(a), read(b), read(c), read(d), read(e), read(f1);
f[x][y] += (a << 1) * W, f[y][x] += (a << 1) * W;
f[y][z] += (b << 1) * W, f[z][y] += (b << 1) * W;
f[z][x] += (c << 1) * W, f[x][z] += (c << 1) * W;
f[0][x] += (d - f1) * W, f[x][m] -= (d - f1) * W;
f[0][y] += (e - d) * W, f[y][m] -= (e - d) * W;
f[0][z] += (f1 - e) * W, f[z][m] -= (f1 - e) * W;
}
fo(i, 1, n) f[0][i] += W, f[i][m] -= W;
fo(i, 1, n) f[0][i] += inf, f[i][0] += inf, f[i][m] += inf, f[m][i] += inf;
fo(i, 1, q) {
read(x), read(y), read(z);
if (z == 0) f[y][x] = INF;
else if (z == 1) f[x][y] = f[y][x] = INF;
else f[0][x] = f[y][m] = INF;
}
ll ans = Sap();
ans -= 1ll * n * inf;
printf("%lld
", ans);
}
return 0;
}