#P9341. 最大收益

    ID: 5729 传统题 2000ms 888MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2400提高+/省选-最小割建模拆点Dinic当前弧优化最大流最小割定理

最大收益

题面翻译

NN 个点 MM 条边的无向图,每个点有两个权值 AiA_i 和 BiB_i。可以用 AiA_i 的代价删除第 ii 个节点。并删除与这个点相连的边。一个极大连通块的权值定义为 BiB_i 的权值和的绝对值。

删除一些节点后,收益定义为所有极大连通块权值之和减去代价和。求最大的可能收益。

样例 #1

样例输入 #1

4 4
4 1 2 3
0 2 -3 1
1 2
2 3
3 4
4 2

样例输出 #1

1

样例 #2

样例输入 #2

10 12
733454 729489 956011 464983 822120 364691 271012 762026 751760 965431
-817837 -880667 -822819 -131079 740891 581865 -191711 -383018 273044 476880
3 1
4 1
6 9
3 8
1 6
10 5
5 6
1 5
4 3
7 1
7 4
10 3

样例输出 #2

2306209

样例 #3

样例输入 #3

4 2
1 1 1 1
1 1 -1 -1
1 2
3 4

样例输出 #3

4

提示

制約

  • 1 ≤ N ≤ 300 1\ \leq\ N\ \leq\ 300
  • 1 ≤ M ≤ 300 1\ \leq\ M\ \leq\ 300
  • 1 ≤ Ai ≤ 106 1\ \leq\ A_i\ \leq\ 10^6
  • −106 ≤ Bi ≤ 106 -10^6\ \leq\ B_i\ \leq\ 10^6
  • 1 ≤ Ui,Vi ≤ N 1\ \leq\ U_i,V_i\ \leq\ N