【SPOJ839】最优标号

Description

给你一张无向图G(V,E)。每个顶点都有一个标号，它是一个[0,2^31-1]内的整数。不同的顶点可能会有相同的标号。
对每条边(u,v)，我们定义其费用cost(u,v)为u的标号与v的标号的异或值。
现在我们知道一些顶点的标号。你需要确定余下顶点的标号使得所有边的费用和尽可能小。

Input

第一行有两个整数N,M(1<=N<=500,0<=M<=3000)，N是图的点数，M是图的边数。
接下来有M行，每行有两个整数u,v，代表一条连接u,v的边。
接下来有一个整数K，代表已知标号的顶点个数。接下来的K行每行有两个整数u,p，代表点u的标号是p。假定这些u不会重复。

Output

输出一行一个整数，即最小的费用和。

Sample Input

3 2
1 2
2 3
2
1 5
3 100

Sample Output

Hint

一个可能的标号方案是：点1标5，点2标4，点3标100.

正解：最小割。

这题真的艹。。我觉得我想太多了，还tm分0和1拆点连边。。

考虑每个二进制位，然后题意就是要你求最小割。。所以只要把原图连好，每条边两边的点，0和1互连，然后如果当前点在当前二进制位下为1，就把它和源点连，否则和汇点连。求出最大流，就是当前二进制位1的个数。

 1 //It is made by wfj_2048~
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <cstring>
 5 #include <cstdlib>
 6 #include <cstdio>
 7 #include <vector>
 8 #include <cmath>
 9 #include <queue>
10 #include <stack>
11 #include <map>
12 #include <set>
13 #define inf (1LL<<60)
14 #define il inline
15 #define RG register
16 #define ll long long
17 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
18 
19 using namespace std;
20 
21 struct edge{ ll nt,to,flow,cap; }g[1000010];
22 
23 struct node{ ll u,v; }G[100010];
24 
25 ll head[1010],d[1010],q[1010],x[1010],y[1010],vis[1010],lk[1010],n,m,k,S,T,num,res,ans;
26 
27 il ll gi(){
28     RG ll x=0,q=1; RG char ch=getchar(); while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();
29     if (ch=='-') q=-1,ch=getchar(); while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar(); return q*x;
30 }
31 
32 il void insert(RG ll from,RG ll to,RG ll cap){ g[++num]=(edge){head[from],to,0,cap},head[from]=num; return; }
33 
34 il ll bfs(RG ll S,RG ll T){
35     memset(d,0,sizeof(d)); RG ll h=0,t=1; q[t]=S,d[S]=1;
36     while (h<t){
37     RG ll x=q[++h];
38     for (RG ll i=head[x];i;i=g[i].nt){
39         RG ll v=g[i].to;
40         if (!d[v] && g[i].cap>g[i].flow){
41         q[++t]=v,d[v]=d[x]+1;
42         if (v==T) return 1;
43         }
44     }
45     }
46     return 0;
47 }
48 
49 il ll dfs(RG ll x,RG ll T,RG ll a){
50     if (x==T || !a) return a; RG ll f,flow=0;
51     for (RG ll i=head[x];i;i=g[i].nt){
52     RG ll v=g[i].to;
53     if (d[v]==d[x]+1 && g[i].cap>g[i].flow){
54         f=dfs(v,T,min(a,g[i].cap-g[i].flow));
55         if (!f){ d[v]=-1; continue; }
56         g[i].flow+=f,g[i^1].flow-=f;
57         flow+=f,a-=f; if (!a) return flow;
58     }
59     }
60     return flow;
61 }
62 
63 il ll maxflow(RG ll S,RG ll T){ RG ll flow=0; while (bfs(S,T)) flow+=dfs(S,T,inf); return flow; }
64 
65 il void work(){
66     n=gi(),m=gi(),S=n+1,T=n+2;
67     for (RG ll i=1;i<=m;++i) G[i].u=gi(),G[i].v=gi();
68     k=gi(); for (RG ll i=1;i<=k;++i) x[i]=gi(),y[i]=gi();
69     for (RG ll len=0,s=1;len<=30;++len,s<<=1){
70     memset(head,0,sizeof(head)); num=1,res=0;
71     for (RG ll i=1;i<=m;++i) insert(G[i].u,G[i].v,1),insert(G[i].v,G[i].u,1);
72     for (RG ll i=1;i<=k;++i)
73         if (y[i]&s) insert(S,x[i],inf),insert(x[i],S,0);
74         else insert(x[i],T,inf),insert(T,x[i],0);
75     ans+=maxflow(S,T)*s;
76     }
77     printf("%lld
",ans); return;
78 }
79 
80 int main(){
81     File("optimalmarks");
82     work();
83     return 0;
84 }