出题人题解 | #小D的剑阵#

原题解链接：https://ac.nowcoder.com/discuss/154293

先将$w,v_0,v_{1}w,v\_0,v\_1$ 求和，然后将选择/不选择视为在此基础上付出代价，问题就转化为了求最小代价。

对于每个约束，考虑如下的一个图，$s,ts,\; t$表示源点和汇点，$x,yx,\; y$表示跟这个约束相关的两把剑，$a,b,c,d,e,fa,b,c,d,e,f$表示权值

将割掉$ss$到某一把剑$xx$的边视为不选择$xx$ ，割掉$xx$到$tt$的边视为选择$xx$。

要使$s,ts,t$不连通，割有四种$a,c\mathrm{，}b,d\mathrm{，}a,e,d\mathrm{，}c,f,ba,c，b,d，a,e,d，c,f,b$(注意逗号)

设 $w_{0}w\_0$ 表示选择$xx$能得到的攻击力， 表示选择$yy$能得到的攻击力，$v_{0}v\_0$ ​ 表示 都选时额外获得的攻击力，$v_{1}v\_1$ ​ 表示$x,yx,y$都不选时额外获得的攻击力，$v_{2}v\_2$ ​ 表示只选一个时扣除的攻击力

可得

$a+c=w_0+w_1+v_0(\mathrm{x},\mathrm{y}a+c=w\_\{0\}+w\_\{1\}+v\_\{0\}(\backslash mathrm\{x\},\; \backslash mathrm\{y\}$, 都不选 $))$

$b+d=v_1(\mathrm{x},\mathrm{y}b+d=v\_\{1\}(\backslash mathrm\{x\},\; \backslash mathrm\{y\}$ 都选 $))$

$a+e+d=w_0+v_0+v_1+v_{2}a+e+d=w\_\{0\}+v\_\{0\}+v\_\{1\}+v\_\{2\}$ (不选 $\mathrm{x}\backslash mathrm\{x\}$ ，选 $\mathrm{y}\backslash mathrm\{y\}$ )

$c+f+b=w_1+v_0+v_1+v_{2}c+f+b=w\_\{1\}+v\_\{0\}+v\_\{1\}+v\_\{2\}$ (选 $\mathrm{x}\backslash mathrm\{x\}$ ，不选 $\mathrm{y}\backslash mathrm\{y\}$ )

只需要求出一组合法的解，人为构造

$e=f=\frac{v0+v1}{2}+v_2,b=d=\frac{v1}{2},a=w_0+\frac{v0}{2},c=w_1+\frac{v0}{2}e=f=\backslash frac\{v\; 0+v\; 1\}\{2\}+v\_\{2\},\; b=d=\backslash frac\{v\; 1\}\{2\},\; a=w\_\{0\}+\backslash frac\{v\; 0\}\{2\},\; c=w\_\{1\}+\backslash frac\{v\; 0\}\{2\}$

最小代价即这张图的最小割

复杂度取决于使用的网络流算法，不过应该是都能通过的

#include <bits/stdc++.h>
using namespace std;

typedef long long lo;

lo n, m, opt, lx, ly, tot = -1, head[1007], he[1007], q[1007], t, de[1007], w[1007], W[1007], ans, v0, v1, v2;

struct in
{
  lo to, ne; lo co;
};
vector<in>ter;

inline void build(lo f, lo l, lo c)
{
  ter.push_back((in) {l, head[f], c}), head[f] = ++tot;
}

inline bool bfs()
{
  queue<int>q;
  memset(de, 0, sizeof(de)), de[0] = 1; q.push(0);
  while (!q.empty()) {
    lo qaq = q.front(); q.pop();
    for (lo i = head[qaq]; i >= 0; i = ter[i].ne)
    {
      lo to = ter[i].to;
      if (ter[i].co && (!de[to]))
        de[to] = de[qaq] + 1, q.push(to);
    }
  }
  return de[t] > 0;
}

lo dfs(lo no, lo fl)
{
  if (no == t || (!fl))
    return fl;
  lo rt = 0, c;
  for (lo &i = he[no]; i >= 0; i = ter[i].ne)
  {
    lo to = ter[i].to;
    if (ter[i].co && de[to] == de[no] + 1)
    {
      c = dfs(to, min(fl, ter[i].co));
      if (c)
      {
        fl -= c, rt += c, ter[i].co -= c, ter[i ^ 1].co += c;
        if (fl <= 0)
          return rt;
      }
    }
  }
  return rt;
}

bool flag[1007];

int main()
{
  scanf("%lld%lld", &n, &m);
  t = n + 1; memset(head, -1, sizeof(head));
  for (int i = 1; i <= n; i ++)
    scanf("%lld", w + i), ans += w[i];
  for (int i = 1; i <= m; i ++)
  {
    scanf("%lld%lld%lld%lld%lld", &lx, &ly, &v0, &v1, &v2);
    ans += v0 + v1;
    W[lx] += v1 / 2, W[ly] += v1 / 2, w[lx] += v0 / 2, w[ly] += v0 / 2;
    build(lx, ly, (v0 + v1) / 2 + v2), build(ly, lx, (v0 + v1) / 2 + v2);
  }
  for (int i = 1; i <= n; i ++)
    build(0, i, w[i]), build(i, 0, 0), build(i, t, W[i]), build(t, i, W[i]);
  lo tmp;
  while (bfs())
  {
    memcpy(he, head, sizeof(he));
    while ((tmp = dfs(0, 1e13 + 7)) > 0)
      ans -= tmp;
  }
  printf("%lld", ans);
  return 0;
}