[bzoj2400]Spoj 839 Optimal Marks 最小割

2400: Spoj 839 Optimal Marks

Time Limit: 10 Sec   Memory Limit: 128 MB [ Submit][ Status][ Discuss]

Description

定义无向图中的一条边的值为：这条边连接的两个点的值的异或值。 定义一个无向图的值为：这个无向图所有边的值的和。 给你一个有 n个结点m条边的无向图。其中的一些点的值是给定的，而其余的点的值由你决定（但要求均为非负数），使得这个无向图的值最小。在无向图的值最小的前提下，使得无向图中所有点的值的和最小。  

Input

第一行 ， 两个数n，m， 表示图的点数和边数 。 接下来n行 ，每行一个数，按编号给出每个点的值（若为负数则表示这个点的值由你决定，值的绝对值大小不超过10^9）。 接下来m行，每行二个数a，b，表示编号为a与b的两点间连一条边。（保证无重边与自环。）  

Output

     第一行，一个数，表示无向图的值。     第二行，一个数，表示无向图中所有点的值的和。  

Sample Input

3 2 2 -1 0 1 2 2 3

Sample Output

2 2

HINT

数据约定   n<=500，m<=2000   样例解释     2结点的值定为0即可。

Source

按二进制跑最小割

S向为0的点连inf

为1的点向T连inf

给出的建无向边

#include<iostream> #include<cstring> #include<cstdio> #define inf 100000000 using namespace std; typedef long long ll; const int N = 505; int last[N],h[N],q[N],bit[35],cnt=1,T,S=0,n,m,K,cur[N],tot,a[N],u[2005],v[2005],va[N]; bool vis[N]; ll ans1,ans2; struct Edge{ int to,next,v; }e[200005]; void insert( int u, int v, int w ){ e[++cnt].to = v; e[cnt].next = last[u]; e[cnt].v = w; last[u] = cnt; e[++cnt].to = u; e[cnt].next = last[v]; e[cnt].v = 0; last[v] = cnt; } bool bfs(){ memset(h,-1,sizeof(h)); int tail = 1, head = 0; q[0] = S; h[S] = 0; while( tail != head ){ int now = q[head++]; for( int i = last[now]; i; i = e[i].next ) if( h[e[i].to] == -1 && e[i].v ){ h[e[i].to] = h[now] + 1; q[tail++] = e[i].to; } } return h[T] != -1; } int dfs( int x, int f ){ int w,used=0; if( x == T ) return f; for( int i = cur[x]; i; i = e[i].next ) if( h[e[i].to] == h[x] + 1 ){ w = dfs(e[i].to,min(e[i].v,f-used)); e[i].v -= w; e[i^1].v += w; used += w; if( e[i].v ) cur[x] = i; if( f == used ) return f; } if( !used ) h[x] = -1; return used; } int dinic(){ int ans = 0; while( bfs() ){ for( int i = S; i <= T; i++ ) cur[i] = last[i]; ans += dfs(S,inf); } return ans; } void build( int x ){ cnt = 1; memset(last,0,sizeof(last)); memset(vis,0,sizeof(vis)); for( int i = 1; i <= n; i++ ) if( a[i] >= 0 ){ if(a[i]&x) insert( i, T, inf ); else insert( S, i, inf ); } for( int i = 1; i <= m; i++ ){ insert( u[i], v[i], 1 ); insert( v[i], u[i], 1 ); } } void dfs( int x ){ vis[x] = 1; for( int i = last[x]; i; i = e[i].next ) if( e[i^1].v && !vis[e[i].to] ) dfs(e[i].to); } int main(){ scanf("%d%d", &n, &m); bit[0] = 1; T = n+1; for( int i = 1; i <= n; i++ ) scanf("%d", &a[i]); for( int i = 1; i <= 30; i++ ) bit[i] = bit[i-1]<<1; for( int i = 1; i <= m; i++ ) scanf("%d%d", &u[i], &v[i]); for( int i = 0; i <= 30; i++ ){ build(bit[i]); ans1 += (ll)bit[i]*dinic(); dfs(T); for( int k = 1; k <= n; k++ ) if( vis[k] ) va[k] += bit[i]; } printf("%lld\n", ans1); for( int i = 1; i <= n; i++ ) if( a[i] > 0 ) ans2 += a[i]; else ans2 += va[i]; printf("%lld", ans2); return 0; }