SP839 OPTM - Optimal Marks

    • 42通过
    • 123提交
  • 题目来源 SPOJ 839
  • 评测方式 RemoteJudge
  • 标签
  • 难度 省选/NOI-
  • 时空限制 1407ms / 1536MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    给你一个无向图G(V,E)。 每个顶点都有一个int范围内的整数的标记。 不同的顶点可能有相同的标记。

    对于边(u,v),我们定义Cost(u,v)= mark [u] xor mark [v]。

    现在我们知道某些节点的标记了。你需要确定其他节点的标记,以使边的总成本尽可能小。

    感谢@耀晨_wcx 提供的翻译

    题目描述

    You are given an undirected graph G(V, E). Each vertex has a mark which is an integer from the range [0..2 $ ^{31} $ – 1]. Different vertexes may have the same mark.

    For an edge (u, v), we define Cost(u, v) = mark[u] xor mark[v].

    Now we know the marks of some certain nodes. You have to determine the marks of other nodes so that the total cost of edges is as small as possible.

    输入输出格式

    输入格式:

    The first line of the input data contains integer T (1 ≤ T ≤ 10) - the number of testcases. Then the descriptions of T testcases follow.

    First line of each testcase contains 2 integers N and M (0 < N <= 500, 0 <= M <= 3000). N is the number of vertexes and M is the number of edges. Then M lines describing edges follow, each of them contains two integers u, v representing an edge connecting u and v.

    Then an integer K, representing the number of nodes whose mark is known. The next K lines contain 2 integers u and p each, meaning that node u has a mark p. It’s guaranteed that nodes won’t duplicate in this part.

    输出格式:

    For each testcase you should print N lines integer the output. The Kth line contains an integer number representing the mark of node K. If there are several solutions, you have to output the one which minimize the sum of marks. If there are several solutions, just output any of them.

    输入输出样例

    输入样例#1: 复制
    1
    3 2
    1 2
    2 3
    2
    1 5
    3 100
    输出样例#1: 复制
    5
    4
    100
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。