题目描述
定义无向图中的一条边的值为：这条边连接的两个点的值的异或值。
定义一个无向图的值为：这个无向图所有边的值的和。
给你一个有n个结点m条边的无向图。其中的一些点的值是给定的，而其余的点的值由你决定（但要求均为非负数），使得这个无向图的值最小。在无向图的值最小的前提下，使得无向图中所有点的值的和最小。
输入
第一行，两个数n，m，表示图的点数和边数。
接下来n行，每行一个数，按编号给出每个点的值（若为负数则表示这个点的值由你决定，值的绝对值大小不超过10^9）。
接下来m行，每行二个数a，b，表示编号为a与b的两点间连一条边。（保证无重边与自环。）
输出
第一行，一个数，表示无向图的值。
第二行，一个数，表示无向图中所有点的值的和。
样例输入
3 2 2 -1 0 1 2 2 3
样例输出
2 2
题解
网络流最小割
由于xor是二进制位运算，因此我们可以拆位处理。
拆位以后每个点只为0或1，相邻的点选择不同则会产生代价，问最小代价。
显然是最小割。
对于每个点，如果它已经确定，则如果其为1则向T连边，如果其为0则S向其连边，容量为inf。
对于相邻的点，相互连边，容量为1。
然后最小割即为第一问答案。
对于第二问答案，有一个神方法，可以直接跑一遍最小割就能算出来。
具体就是原来的1全部改为10000，然后S向所有点，容量为1。跑最小割时，肯定要保证割10000边的条数最小，即为第一问答案；而在此基础上每有一个数为1，则需要额外割一条1边，所以同时让割1边的条数最小，也就保证了1的个数最少。
最后把每一位的结果加起来即为答案。注意要开long long。
#include#include #include #define N 510#define M 20010using namespace std;typedef long long ll;const int inf = 1 << 30;queue q;int n , m , v[N] , x[M] , y[M] , head[N] , to[M] , val[M] , next[M] , cnt , s , t , dis[N];ll ans1 , ans2;void add(int x , int y , int z){ to[++cnt] = y , val[cnt] = z , next[cnt] = head[x] , head[x] = cnt; to[++cnt] = x , val[cnt] = 0 , next[cnt] = head[y] , head[y] = cnt;}bool bfs(){ int x , i; memset(dis , 0 , sizeof(dis)); while(!q.empty()) q.pop(); dis[s] = 1 , q.push(s); while(!q.empty()) { x = q.front() , q.pop(); for(i = head[x] ; i ; i = next[i]) { if(val[i] && !dis[to[i]]) { dis[to[i]] = dis[x] + 1; if(to[i] == t) return 1; q.push(to[i]); } } } return 0;}int dinic(int x , int low){ if(x == t) return low; int temp = low , i , k; for(i = head[x] ; i ; i = next[i]) { if(val[i] && dis[to[i]] == dis[x] + 1) { k = dinic(to[i] , min(temp , val[i])); if(!k) dis[to[i]] = 0; val[i] -= k , val[i ^ 1] += k; if(!(temp -= k)) break; } } return low - temp;}void solve(int k){ int i , c = 0; memset(head , 0 , sizeof(head)) , cnt = 1; for(i = 1 ; i <= n ; i ++ ) { add(s , i , 1); if(v[i] >= 0) { if(v[i] & k) add(i , t , inf); else add(s , i , inf); } } for(i = 1 ; i <= m ; i ++ ) add(x[i] , y[i] , 10000) , add(y[i] , x[i] , 10000); while(bfs()) c += dinic(s , inf); ans1 += (ll)c / 10000 * k , ans2 += (ll)c % 10000 * k;}int main(){ int i; scanf("%d%d" , &n , &m) , s = 0 , t = n + 1; for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &v[i]); for(i = 1 ; i <= m ; i ++ ) scanf("%d%d" , &x[i] , &y[i]); for(i = 1 << 30 ; i ; i >>= 1) solve(i); printf("%lld\n%lld\n" , ans1 , ans2); return 0;}