首先发现每一位二进制可以分开来做。
然后就变成0、1两种数了，考虑最小割。
设S表示选0，T表示选1，则
对于确定的点向数字对应的S/T连边，边权inf；然后原来图中有边的，互相连边，边权为1。
直接最小割即可，最后还要dfs一下来求出每个未确定的数选的是0还是1。
1 /************************************************************** 2 Problem: 2400 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:552 ms 7 Memory:3180 kb 8 ****************************************************************/ 9 10 #include11 #include 12 #include 13 14 using namespace std; 15 typedef long long ll; 16 const int N = 505; 17 const int M = 2005; 18 const int Me = 200005; 19 const int inf = 1e9; 20 21 struct edge { 22 int x, y; 23 edge() {} 24 edge(int _x, int _y) : x(_x), y(_y) {} 25 } E[M]; 26 27 struct edges { 28 int next, to, f; 29 edges() {} 30 edges(int _n, int _t, int _f) : next(_n), to(_t), f(_f) {} 31 } e[Me]; 32 33 int n, m, S, T; 34 int a[N], del[N]; 35 int tot, first[N]; 36 int d[N], q[N]; 37 ll ans; 38 39 inline int read() { 40 int x = 0, sgn = 1; 41 char ch = getchar(); 42 while (ch < '0' || '9' < ch) { 43 if (ch == '-') sgn = -1; 44 ch = getchar(); 45 } 46 while ('0' <= ch && ch <= '9') { 47 x = x * 10 + ch - '0'; 48 ch = getchar(); 49 } 50 return sgn * x; 51 } 52 53 inline void Add_Edges(int x, int y, int f) { 54 e[++tot] = edges(first[x], y, f), first[x] = tot; 55 e[++tot] = edges(first[y], x, 0), first[y] = tot; 56 } 57 58 bool bfs() { 59 int l, r, x, y; 60 memset(d, 0, sizeof(d)); 61 d[q[1] = S] = 1; 62 for (l = r = 1; l != (r + 1) % N; (++l) %= N) 63 for (x = first[q[l]]; x; x = e[x].next) 64 if (!d[y = e[x].to] && e[x].f) 65 d[q[(++r) %= N] = y] = d[q[l]] + 1; 66 return d[T]; 67 } 68 69 int dfs(int p, int lim) { 70 if (p == T || !lim) return lim; 71 int x, y, tmp, rest = lim; 72 for (x = first[p]; x; x = e[x].next) 73 if (d[y = e[x].to] == d[p] + 1 && (tmp = min(e[x].f, rest) > 0)) { 74 rest -= (tmp = dfs(y, tmp)); 75 e[x].f -= tmp, e[x ^ 1].f += tmp; 76 if (!rest) return lim; 77 } 78 if (lim == rest) d[p] = 0; 79 return lim - rest; 80 } 81 82 int Dinic() { 83 int res = 0; 84 while (bfs()) 85 res += dfs(S, inf); 86 return res; 87 } 88 89 void build_graph(int t) { 90 int i; 91 tot = 1, memset(first, 0, sizeof(first)); 92 for (i = 1; i <= n; ++i) 93 if (a[i] >= 0) 94 if (a[i] & t) Add_Edges(i, T, inf); 95 else Add_Edges(S, i ,inf); 96 for (i = 1; i <= m; ++i) 97 Add_Edges(E[i].x, E[i].y, 1), Add_Edges(E[i].y, E[i].x, 1); 98 } 99 100 void find(int p) {101 int x, y;102 d[p] = 1;103 for (x = first[p]; x; x = e[x].next)104 if (e[x ^ 1].f && !d[y = e[x].to]) find(y);105 }106 107 void calc_val(int t) {108 int i;109 memset(d, 0, sizeof(d));110 find(T);111 for (i = 1; i <= n; ++i)112 if (d[i]) del[i] += t;113 }114 115 ll calc_ans() {116 ll res = 0;117 int i;118 for (i = 1; i <= n; ++i)119 res += a[i] >= 0 ? a[i] : del[i];120 return res;121 }122 123 int main() {124 int i;125 n = read(), m = read();126 S = n + 1, T = n + 2;127 for (i = 1; i <= n; ++i)128 a[i] = read();129 for (i = 1; i <= m; ++i)130 E[i] = edge(read(), read());131 for (i = 0; i <= 30; ++i) {132 build_graph(1 << i);133 ans += (ll) (1 << i) * Dinic();134 calc_val(1 << i);135 }136 printf("%lld\n%lld\n", ans, calc_ans());137 return 0;138 }