BZPRO

#5448. 变量

内存限制：256 MiB 时间限制：3 Sec
提交 提交记录 讨论

题目描述

有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)。

输入格式

第一行一个整数t表示数据组数。
每组数据第一行四个整数n,W,p,q表示节点数。
接下来p行每行九个整数xi,yi,zi,ai,bi,ci,di,ei,fi。
接下来q行每行三个整数x,y,r。
r=0表示w[x]<=w[y]；r=1表示w[x]=w[y]；r=2表示w[x]<w[y]。
保证存在方案。
t<=10，n<=500，p,q<=1000，1<=W<=10^6，
0<=ai,bi,ci,di,ei,fi<=1000。

输出格式

每组数据输出一行一个整数表示sigma(wi)+sigma(Hi)的最小值。

样例

样例输入


			
1

3 1 1 1

1 2 3 1 1 1 1 1 1 

1 2 2

样例输出


			
3

数据范围与提示

BZPRO Powered by Remmina.
Github Repository