最优标号问题

解题思路

本题给我们一个无向图，然后我们给没有标号的点进行标号，使得所有边的费用和最小。

每条边的费用是两个端点标号的异或和，异或运算是按位运算，因此我们可以每一位单独看，最终的费用和应该是每一位的和加起来。

由于每一位完全独立，因此最终费用和的最小值其实就是求每一位的最小值，再合在一起，就是答案。

由于每一位只有 $0$ 和 $1$ 两种可能，因此所有点可以分成两类，一类是 $0$，一类是 $1$。

然后看一下点与点之间的边有哪些情况，$0$ 和 $0$ 之间的边费用就是 $0$，$1$ 和 $1$ 之间的边费用就是 $0$，$0$ 和 $1$ 之间的边费用就是 $1$。

由此可以发现，当两类集合中的点确定之后，整个费用和的最小值就等于两个集合之间的边的数量最小值，也就是割。

假设现在要计算第 $k$ 位，若第 $k$ 位中的两个集合之间的边的最小数量是 $m$，也就是有 $m$ 个数第 $k$ 位是 $1$，一个数第 $k$ 位是 $1$ 的费用是 $2^k$，那么 $m$ 个的费用就是 $m \cdot 2^k$

因此如果考虑第 $k$ 位，就是要将所有点的第 $k$ 位分成两类，使得两类之间的边的数量最小，这个问题和流网络中的割非常相似。

我们将原图的无向边都在流网络里建两条有向边。然后我们对点集做一个划分，可以对应到流网络里割的划分。原问题中两个点集之间的边的权值之和就可以对应到两个割之间的割的容量。由于割的容量只会算一个方向，所以权值和也只会算一次，因此原问题中对所有点的划分方式都可以对应到割的划分方式，因此最小费用和就等于最小割（将中间的边的容量设为 $1$）。

求最小割还需要一个源点和汇点，我们可以建立虚拟源点和虚拟汇点。

有些点最开始是有编号的，如果有些点的标号是 $0$，说明他一定要和源点在一个集合，那么我们就从源点向这些点连一条容量是 $+\infty$ 的边，这样这些点就一定能从源点走到，这些点就必然不会和汇点在同一个集合，否则源点和汇点就在同一个集合，就矛盾了。如果有些点的标号是 $1$，说明这些点就必须和汇点在一个集合，同理从这些点向汇点连一条容量是 $+\infty$ 的边。

至于剩下的没有标号的点，有可能和源点一个集合也有可能和汇点一个集合，我们就不做多余的操作了，求最小割的时候按照最优情况分配即可。

综上所述，我们只需要对于每一位分别去求一下最小割，那么每一位的费用就一定是最小的，把每一位的费用加到一块就是总费用的最小值。

本题并没有要求合法方案，这里也可以说明一下，对于每一位，能从源点走到的点都一定和源点在一个集合，能走到汇点的点都一定和汇点在一个集合，通过搜索就能将所有点分成两类，和源点一类的点这一位都选 $0$，和汇点一类的点这一位都选 $1$，这样就能确定每个点每一位的值，得出整个的方案。

注意，本题是无向图，无向边我们就建两条有向边即可，但是在残量网络中每条边有一个反向边，一条无向边会变成四条边，这里和前面一样采用合并的方式合成两条边。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 510, M = (3000 + 500) * 2 + 10, INF = 0x3f3f3f3f;

int n, m, k, S, T;
int h[N], e[M], w[M], ne[M], idx; //邻接表
int q[N], d[N], cur[N]; //队列、层数、当前弧
int p[N]; //记录每个点的标号，-1 表示没有标号
PII edges[3010]; //存储所有边

void add(int a, int b, int c, int d) //添加边
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
    e[idx] = a, w[idx] = d, ne[idx] = h[b], h[b] = idx++;
}

void build(int k) //建图
{
    //初始化邻接表
    memset(h, -1, sizeof h);
    idx = 0;

    for(int i = 0; i < m; i++) add(edges[i].first, edges[i].second, 1, 1); //建无向边

    for(int i = 1; i <= n; i++) //枚举所有点
        if(p[i] >= 0) //如果当前点有标号，直接确定所在集合
        {
            if(p[i] >> k & 1) add(i, T, INF, 0); //和汇点在一个集合，从该点向汇点连一条容量是 INF 的边
            else add(S, i, INF, 0); //和源点在一个集合，从源点向该点连一条容量是 INF 的边
        }
}

bool bfs() //建立分层图，判断是否存在增广路径
{
    int hh = 0, tt = 0;
    q[0] = S;

    memset(d, 0, sizeof d);
    d[S] = 1;

    cur[S] = h[S];

    while(hh <= tt)
    {
        int t = q[hh++];

        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];

            if(!d[j] && w[i])
            {
                d[j] = d[t] + 1;
                cur[j] = h[j];

                if(j == T) return true;

                q[++tt] = j;
            }
        }
    }
    return false;
}

int find(int u, int flow) //统计从 u 往终点能传输的最大流量，上限为 flow
{
    if(u == T) return flow;

    int rest = flow;
    for(int i = cur[u]; i != -1 && rest; i = ne[i])
    {
        cur[u] = i;

        int j = e[i];
        if(d[j] == d[u] + 1 && w[i])
        {
            int k = find(j, min(rest, w[i]));
            if(!k) d[j] = 0;

            w[i] -= k;
            w[i ^ 1] += k;
            rest -= k;
        }
    }
    return flow - rest;
}

LL dinic(int k) //求第 k 位的最小割
{
    build(k); //每次重新建图

    int maxf = 0, flow;
    while(bfs())
        while(flow = find(S, INF)) maxf += flow;
    return maxf;
}

int main()
{
    scanf("%d%d", &n, &m);

    S = 0, T = n + 1; //源点、汇点
    for(int i = 0; i < m; i++) scanf("%d%d", &edges[i].first, &edges[i].second);

    scanf("%d", &k);
    memset(p, -1, sizeof p); //初始化所有标号
    while(k--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        p[a] = b;
    }

    LL res = 0; //记录最小总费用
    for(int i =  0; i < 31; i++) res += dinic(i) << i; //累加每一位的最小费用
    printf("%lld\n", res);

    return 0;
}