[SPOJ839]最优标号

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file optimalmarks.in Output file optimalmarks.out

【题目描述】

给你一张无向图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