OI题库

【题目描述】

给你一张无向图G(V,E)。每个顶点都有一个标号，它是一个[0,2^31-1]内的整数。不同的顶点可能会有相同的标号。

对每条边(u,v)，我们定义其费用cost(u,v)为u的标号与v的标号的异或值。

现在我们知道一些顶点的标号。你需要确定余下顶点的标号使得所有边的费用和尽可能小。

【输入格式】

输入文件的第一行有两个整数N,M(1<=N<=500,0<=M<=3000)，N是图的点数，M是图的边数。

接下来有M行，每行有两个整数u,v，代表一条连接u,v的边。

接下来有一个整数K，代表已知标号的顶点个数。接下来的K行每行有两个整数u,p，代表点u的标号是p。假定这些u不会重复。

【输出格式】

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

【样例输入】

3 2

1 2

2 3

2

1 5

3 100

【样例输出】

97

【提示】

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

SPOJ上原题的输入输出格式和这里有所不同。

【来源】

SPOJ 839 Optimal Marks

Resource: Guo HuaYang