活動 - AcWing

給定一個無向圖?G=(V,E)，每個頂點都有一個標號，它是一個?[0,2^31?1] 內的整數。

不同的頂點可能會有相同的標號。

對每條邊?(u,v)，我們定義其費用?cost(u,v) 為?u?的標號與?v?的標號的異或值。

現在我們知道一些頂點的標號。

你需要確定余下頂點的標號使得所有邊的費用和盡可能小。

輸入格式

第一行有兩個整數?N,M，N?是圖的點數，M?是圖的邊數。

接下來有?M?行，每行有兩個整數?u,v，代表一條連接?u,v 的邊。

接下來有一個整數?K，代表已知標號的頂點個數。

接下來的?K?行每行有兩個整數?u,p，代表點?u?的標號是?p。

假定這些?u?不會重復。

所有點編號從?1?到?N。

輸出格式

輸出一行一個整數，即最小的費用和。

數據范圍

1≤N≤500,
0≤M≤3000,
1≤K≤N

輸入樣例：

3 2
1 2
2 3
2
1 5
3 100

輸出樣例：

97

?解析：

本題給我們一個無向圖，然后我們給沒有標號的點進行標號，使得所有邊的費用和最小。

每條邊的費用是兩個端點標號的異或和，異或運算是按位運算，因此我們可以每一位單獨看，最終的費用和應該是每一位的和加起來。

由于每一位完全獨立，因此最終費用和的最小值其實就是求每一位的最小值，再合在一起，就是答案。

由于每一位只有 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?2^k 因此如果考慮第 k?位，就是要將所有點的第 k?位分成兩類，使得兩類之間的邊的數量最小，這個問題和流網絡中的割非常相似。

我們將原圖的無向邊都在流網絡里建兩條有向邊。然后我們對點集做一個劃分，可以對應到流網絡里割的劃分。原問題中兩個點集之間的邊的權值之和就可以對應到兩個割之間的割的容量。由于割的容量只會算一個方向，所以權值和也只會算一次，因此原問題中對所有點的劃分方式都可以對應到割的劃分方式，因此最小費用和就等于最小割（將中間的邊的容量設為 1）。

求最小割還需要一個源點和匯點，我們可以建立虛擬源點和虛擬匯點。

有些點最開始是有編號的，如果有些點的標號是 0，說明他一定要和源點在一個集合，那么我們就從源點向這些點連一條容量是 +∞?的邊，這樣這些點就一定能從源點走到，這些點就必然不會和匯點在同一個集合，否則源點和匯點就在同一個集合，就矛盾了。如果有些點的標號是 1，說明這些點就必須和匯點在一個集合，同理從這些點向匯點連一條容量是 +∞?的邊。

至于剩下的沒有標號的點，有可能和源點一個集合也有可能和匯點一個集合，我們就不做多余的操作了，求最小割的時候按照最優情況分配即可。

綜上所述，我們只需要對于每一位分別去求一下最小割，那么每一位的費用就一定是最小的，把每一位的費用加到一塊就是總費用的最小值。

本題并沒有要求合法方案，這里也可以說明一下，對于每一位，能從源點走到的點都一定和源點在一個集合，能走到匯點的點都一定和匯點在一個集合，通過搜索就能將所有點分成兩類，和源點一類的點這一位都選 0，和匯點一類的點這一位都選 1，這樣就能確定每個點每一位的值，得出整個的方案。

注意，本題是無向圖，無向邊我們就建兩條有向邊即可，但是在殘量網絡中每條邊有一個反向邊，一條無向邊會變成四條邊，這里和前面一樣采用合并的方式合成兩條邊。

作者：小小_88
鏈接：https://www.acwing.com/solution/content/128199/
來源：AcWing
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。

此作者的題解都寫得非常好，因此我就直接引用此題解。

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
#include<unordered_set>
#include<bitset>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 5e2 + 5, M = (3e3 + N)*2 + 10, INF = 0x3f3f3f3f;
int n, m, K, S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], cur[N];
int p[N];
struct edge{int a, b;
}edges[M];void add(int a, int b, int c1, int c2) {e[idx] = b, f[idx] = c1, ne[idx] = h[a], h[a] = idx++;e[idx] = a, f[idx] = c2, ne[idx] = h[b], h[b] = idx++;
}void build(int x) {memset(h, -1, sizeof h);idx = 0;for (int i = 1; i <= m; i++) {add(edges[i].a, edges[i].b, 1, 1);}for (int i = 1; i <= n; i++) {if (p[i] >= 0) {if (p[i] >> x & 1)add(i, T, INF, 0);else add(S, i, INF, 0);}}
}bool bfs() {int hh = 0, tt = 0;memset(d, -1, sizeof d);q[0] = S, d[S] = 0, 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] == -1 && f[i]) {d[j] = d[t] + 1;cur[j] = h[j];if (j == T)return 1;q[++tt] = j;}}}return 0;
}int find(int u, int limit) {if (u == T)return limit;int flow = 0;for (int i = cur[u]; i != -1 && flow < limit; i = ne[i]) {int j = e[i];cur[u] = i;if (d[j] == d[u] + 1 && f[i]) {int t = find(j, min(f[i], limit - flow));if (!t)d[j] = -1;f[i] -= t, f[i ^ 1] += t, flow += t;}}return flow;
}LL dinic(int x) {build(x);LL ret = 0, flow;while (bfs())while (flow = find(S, INF)) {ret += flow;}return ret;
}int main() {scanf("%d%d", &n, &m);S = 0, T = n + 1;for (int i = 1, a, b; i <= m; i++) {scanf("%d%d", &edges[i].a, &edges[i].b);}cin >> K;memset(p, -1, sizeof p);for (int i = 1,a,b; i <= K; i++) {scanf("%d%d", &a, &b);p[a] = b;}LL ret = 0;for (int i = 0; i <= 30; i++) ret += dinic(i) << i;cout << ret << endl;return 0;
}

?