题目描述

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

样例

略

算法1

图的拓扑结构没变，所以修改 f 替代重建图

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N=510, M=(3000+N*2)*2, inf=1e8;
int ver[M],f[M],w[M],nxt[M],head[N],tot=1;
int d[N],q[N],nh[N],n,m,K,S,T;
struct {int idx,val;} knew[N];

void add(int a,int b,int c1,int c2){
    ver[++tot]=b, f[tot]=c1, nxt[tot]=head[a], head[a]=tot;
    ver[++tot]=a, f[tot]=c2, nxt[tot]=head[b], head[b]=tot;
}

bool bfs(){
    memset(d,0,sizeof d);
    int hh=0,tt=1;
    d[S]=1, q[hh]=S, nh[S]=head[S];
    while(hh<tt){
        int x=q[hh++];
        for(int i=head[x];i;i=nxt[i]){
            int y=ver[i];
            if(d[y] || !f[i])continue;
            d[y]=d[x]+1;
            nh[y]=head[y];
            if(y==T)return true;
            q[tt++]=y;
        }
    }
    return false;
}

int find(int x,int limit){
    if(x==T)return limit;
    int flow=0;
    for(int i=nh[x];i && flow<limit;i=nxt[i]){
        int y=ver[i];
        nh[x]=i;
        if(d[y]!=d[x]+1 || !f[i])continue;
        int t=find(y,min(f[i],limit-flow));
        if(!t) d[y]=0;
        f[i]-=t, f[i^1]+=t, flow+=t;
    }
    return flow;
}

void build(int k){
    fill(f+2,f+tot+1,1);
    for (int i=1; i<=K; i ++ ){ //修改对应的f
        int idx=knew[i].idx;
        f[idx+1]=f[idx+2]=f[idx+3]=f[idx+4]=0;
        if(knew[i].val>>k & 1) f[idx+3]=inf;
        else                   f[idx+1]=inf;
    }
}

long long dinic(int k){
    build(k);
    int res=0,flow;
    for(;bfs();)
        while(flow=find(S,inf))res+=flow;
    return res;
}

int main(){
    cin>>n>>m;
    S=0, T=n+1;
    for(int i = 0; i < m; i ++ ) {
        int x,y;
        cin>>x>>y;
        add(x,y,1,1);
    }
    cin>>K;
    for(int i=1;i<=K;i++){
        int x,y;
        cin>>x>>y;
        knew[i]={tot,y}; //接下来的4个f[]是knew[i]的对应f
        add(S,x,0,0), add(x,T,0,0);
    }

    long long res=0;
    for (int i=0; i<=30; i++ )  res += dinic(i)<<i;
    printf("%lld\n", res);
    return 0;
}