#P9317. 障碍设置(最小割求方案)

    ID: 5622 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 6 上传者: 标签>CF2000提高拆点限制点容量最小割建模Dinic当前弧优化残量网络最大流最小割定理

障碍设置(最小割求方案)

题面翻译

题目描述

给定一张 nn 个点 mm 条边的连通无向图,要求在某些点(不能为 11 号点或者 nn 号点)设立障碍,在 ii 号点建立障碍的费用为 cic_i,要使得 11 号点和 nn 号点不连通,求最小花费的方案。

输入格式

第一行两个整数 $n,m(3\leq n\leq 100,n−1\leq m\leq \frac{n(n−1)}{2}−1)$。

接下来 mm 行,每行两个数 ai,bi(1≤ai<bi≤n)a_i,b_i(1\leq ai < bi\leq n),保证没有重边自环,并且 11 与 nn 不直接相连。

接下来一行 nn 个整数 c1,c2,…,cn(0≤ci≤109)c_1,c_2,…,c_n(0\le ci\le 10^9),保证 c1=cn=0c_1=c_n=0。

输出格式

第一行输出一个数,表示最小的花费。

接下来输出一个数 kk,表示建立障碍的个数。接下来一行 kk 个数,表示建立障碍的 kk 个点。

样例 #1

样例输入 #1

5 5
1 2
2 3
3 5
2 4
4 5
0 8 3 4 0

样例输出 #1

7
2
3 4

样例 #2

样例输入 #2

3 2
1 2
2 3
0 1 0

样例输出 #2

1
1
2

样例 #3

样例输入 #3

5 9
1 2
1 3
1 4
2 3
2 4
2 5
3 4
3 5
4 5
0 1000000000 1000000000 1000000000 0

样例输出 #3

3000000000
3
2 3 4

提示

制約

  • 3 ≤ N ≤ 100 3\ \leq\ N\ \leq\ 100
  • N − 1 ≤ M ≤ N(N−1)2 − 1 N\ -\ 1\ \leq\ M\ \leq\ \frac{N(N-1)}{2}\ -\ 1
  • 1 ≤ ai < bi ≤ N 1\ \leq\ a_i\ \lt\ b_i\ \leq\ N (1 ≤ i ≤ M) (1\ \leq\ i\ \leq\ M)
  • (ai, bi) ≠ (1, N) (a_i,\ b_i)\ \neq\ (1,\ N)
  • 1 ≤ ci ≤ 109 1\ \leq\ c_{i}\ \leq\ 10^9 (2 ≤ i ≤ N−1) (2\ \leq\ i\ \leq\ N-1)
  • c1 = cN = 0 c_1\ =\ c_N\ =\ 0