题目描述
定义无向图中的一条边的值为：这条边连接的两个点的值的异或值。定义一个无向图的值为：这个无向图所有边的值的和。给你一个有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 <cstdio>
#include <cstring>
#include <queue>
#define N 510
#define M 20010
using namespace std;
typedef long long ll;
const int inf = 1 << 30;
queue<int> 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;
}
