当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

6142:Jedi Council

题目描述
> A Jedi Council was an organized body of Jedi, typically Masters, serving the Jedi Order as an administrative body that governed the Order's academies, temples, and organizations such as the Jedi Service Corps.
>
> All of the Coruscant Councils appointed their own members through unanimous vote, and each had a designated leader. Governing for several centuries, all four Councils were dissolved in 19 BBY following the Sith plot known as Operation: Knightfall and Order 66, both military operations carried out legally by the Grand Army of the Republic.
>
> — Wookieepedia

The masters of Jedi Council are controversial with approving the proposal of Chancellor Palpatine that the Republic should build a clone army to fight against the separatist attacks after the Naboo Crisis. There has been debates about the proposal, but only a few had a slight feeling of the presence of the coming darkness. Largely, the result of this debate is manipulated by the Dark Lord.

This problem is about how the result of the debate is being changed.

The masters in the Jedi Council are either *aggressive* or *permissive*, and each will vote for his/her opinions. Suppose that there are $n$ masters in the Council and the $i$-th master has an opinion score $w_i$ of either $+W$ (for an aggressive master), or $-W$ (for an permissive master).

Jedi masters may have influences on each other. Given three masters $x_i$, $y_i$, and $z_i$ and parameters $a_i,b_i,c_i,d_i,e_i,f_i$, the level of influence is computed by

$$H_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}),$$

where $w_{x_i}$, $w_{y_i}$, and $w_{z_i}$ are the opinion scores of $x_i$, $y_i$, $z_i$, respectively.

Suppose that there are $p$ influences. The opinion of the Jedi Council is determined by:

$$\mathcal{O}=\sum_{i=1}^n w_i + \sum_{i=1}^p H_i$$

The Dark Lord can silently influence the opinions of Jedi masters. He chose a subset of the masters and silently changed their minds (from aggressive to permissive, or from permissive to aggressive).

Furthermore, there are balances and Force bonds between the masters which should not be broken, otherwise the evil plan will be revealed by the cautious master Yoda. In particular, there are constraints over the opinions in the form of $w_x \le w_y$, $w_x = w_y$, or $w_x < w_y$.

Nobody knows the true opinion of the Jedi masters. The only thing we knew is that the Dark Lord is a true master of combinatorial optimization that had changed the minds of the masters such that the opinion of the entire Jedi Council (i.e., the value of $\mathcal{O}$) is minimized, at the same time no constraint is violated.

It is the time for you to reveal the evil process of the Dark Lord. Given the constraints, you should find a plan that minimizes the Jedi Council's opinion.
输入解释
The first line of the input contains an integer $T$.

For each test case, the first line contains four integers $n$ the number of Jedi masters ($1\le n \le 500$), $W$ the absolute value of their opinion scores ($0\le W \le 10^6$), $p$ the number of influences between Jedi masters ($0\le p \le 1000$), $q$ the number of constraints ($0\le n \le 1000$).

Then $p$ lines follows, each contains $9$ integers $x_i, y_i, z_i, a_i, b_i, c_i, d_i, e_i, f_i$, as mentioned in the problem ($1\le x_i,y_i,z_i\le n$, $0\le a_i, b_i, c_i, d_i, e_i, f_i \le 1000$).

The following $q$ lines describe the constraints, each line contains three integers, $x, y, r$.

* $r = 0$ indicates a constraint in the form of $w_x \le w_y$.
* $r = 1$ indicates a constraint in the form of $w_x = w_y$.
* $r = 2$ indicates a constraint in the form of $w_x \lt w_y$.

The input guarantees at least one solution exists.
输出解释
Output one line for each test case, the minimized Jedi Council’s opinion.
输入样例
1
3 1 1 1
1 2 3 1 1 1 1 1 1 
1 2 2
输出样例
3
来自杭电HDUOJ的附加信息
Recommend liuyiding

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-6142

最后修改于 2020-10-25T23:28:42+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
2000/1000MS(Java/Others) 65536/65536K(Java/Others)