题意：
定义无向图中的一条边的值为：这条边连接的两个点的值的异或值。
定义一个无向图的值为：这个无向图所有边的值的和。
给你一个有n个结点m条边的无向图。其中的一些点的值是给定的，而其余的点的值由你决定（但要求均为非负数），使得这个无向图的值最小。在无向图的值最小的前提下，使得无向图中所有点的值的和最小。
思路：
最小割 按位做 枚举每一位 一个点与S联通表示这个点选0，与T联通表示这个点选1 如果这个点为0，那么源点S向这个点连一条容量为inf的边 如果这个点为1，那么这个点向汇点T连一条容量为inf的边 每条边对应连一条容量为1的边 考虑点权的话非常巧妙，本来两个条件应该是费用流的？ 但是可以通过一些技巧用最小割来实现 把原来的边容量放大10000倍 如果一个点不和S直接连边，那么源点S向这个点连一条容量为1的边 这样割掉这条边要花1的费用 为什么是对的呢？因为小边是不会影响大边的，一定是在大边最小的情况下，才会考虑小边，就等价于在边权和最小的情况下，考虑点权和 ans/10000是最小边权和，ans%10000是最小点权和
注意关系的边应该连双向。
#include <bits/stdc++.h> using namespace std; typedef long long LL; typedef LL lint; const lint inf = 0x3f3f3f3f3f3f3f3f; const int maxn = 505; const int maxm = 20005; struct dinic{ static const int N = 1005; static const int M = 200005; static const lint inf = 0x3f3f3f3f3f3f3f3f; int he[N],ne[M],ver[M],d[N]; lint edge[M]; int s,t,tot; queue<int> que; void init( int n ){ for( int i = 0;i <= n;i++ ){ he[i] = 0; } tot = 1; } void add( int x,int y,lint z ){ ver[++tot] = y; ne[ tot ] = he[x]; he[x] = tot; edge[ tot ] = z; ver[++tot] = x; ne[tot] = he[y]; he[y] = tot;edge[tot] = 0; } bool bfs(){ memset( d,0,sizeof( d ) ); while( que.size() ) que.pop(); que.push( s ); d[s] = 1; while( que.size() ){ int x = que.front(); que.pop(); for( int cure = he[x];cure;cure = ne[cure] ){ int y = ver[cure]; if( edge[cure] && !d[y] ){ que.push( y ); d[ y ] = d[x] + 1; if( y == t ) return 1; } } } return 0; } lint dfs( int x,lint flow ){ if( x== t ) return flow; lint rest = flow,k; for( int cure = he[x];cure && rest;cure = ne[cure] ){ int y = ver[cure]; if( edge[cure] && d[ y ] == d[x] + 1 ){ k = dfs( y,min( rest,edge[cure] ) ); if( !k ) d[ y ] = 0; edge[cure] -= k; edge[ cure^1 ] += k; rest -= k; } } return flow - rest; } lint max_flow( int x,int y ){ s = x; t = y; lint maxflow = 0; lint flow = 0; while( bfs() ) while( flow = dfs( s,inf ) ) maxflow += flow; return maxflow; } } g[31]; int a[maxn]; typedef pair<int,int> pii; pii e[maxm]; int S,T,n,m; void build( int k ){ for( int i = 1;i <= n;i++ ){ if( a[i] >= 0 ){ if( a[i]>>k&1 ){ g[k].add(i,T,inf); g[k].add(S,i,1); }else g[k].add(S,i,inf); }else g[k].add(S,i,1); } for( int i = 1;i <= m;i++ ){ if( e[i].first > e[i].second )g[k].add(e[i].first,e[i].second,10000); else g[k].add( e[i].second,e[i].first,10000 ); } } int main(){ scanf("%d%d",&n,&m); S = 0,T = n+1; for( int i = 0;i <= 30;i++ ) g[i].init(T); for( int i = 1;i <= n;i++ )scanf("%d",&a[i]); for( int x,y,i = 1;i <= m;i++ ){ scanf("%d%d",&x,&y); e[i].first = x;e[i].second = y; } for( int i = 0;i <= 30;i++ ) build(i); LL ans1 = 0,ans2 = 0; for( int i = 0;i <= 30;i++ ){ LL res = g[i].max_flow(S,T); LL o = 1LL<<i; ans1 += o*(res/10000); ans2 += o*(res%10000); } printf("%lld\n%lld\n",ans1,ans2); return 0; }
