电脑优化,青岛市做网站优化,开封网站制作,我要素材网网页设计素材活动 - AcWing
给定一个无向图 G(V,E)#xff0c;每个顶点都有一个标号#xff0c;它是一个 [0,2^31−1] 内的整数。
不同的顶点可能会有相同的标号。
对每条边 (u,v)#xff0c;我们定义其费用 cost(u,v) 为 u 的标号与 v 的标号的异或值。
现在我们知道一些顶点的标号…活动 - AcWing
给定一个无向图 G(V,E)每个顶点都有一个标号它是一个 [0,2^31−1] 内的整数。
不同的顶点可能会有相同的标号。
对每条边 (u,v)我们定义其费用 cost(u,v) 为 u 的标号与 v 的标号的异或值。
现在我们知道一些顶点的标号。
你需要确定余下顶点的标号使得所有边的费用和尽可能小。
输入格式
第一行有两个整数 N,MN 是图的点数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 之间的边费用就是 01 和 1 之间的边费用就是 00 和 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 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。 此作者的题解都写得非常好因此我就直接引用此题解。
#includeiostream
#includestring
#includecstring
#includecmath
#includectime
#includealgorithm
#includeutility
#includestack
#includequeue
#includevector
#includeset
#includemath.h
#includemap
#includesstream
#includedeque
#includeunordered_map
#includeunordered_set
#includebitset
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pairint, 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;
}
