Project1

标题: 最近迷上了一款叫Kami的游戏，然而并不会玩... (QAQ) [打印本页]

作者: M.Winderic. 时间: 2017-4-15 22:11
标题: 最近迷上了一款叫Kami的游戏，然而并不会玩... (QAQ)
本帖最后由 M.Winderic. 于 2017-4-15 22:34 编辑

游戏规则是酱紫的：

平面中有一连续区域由三角形组成，每次操作选择一个三角形，
将被选中的三角形以及与其相邻的具有相同颜色的三角形染成另一种颜色。
当区域内仅剩一种颜色时就过关啦~

[line]2[/line]

然而这太烧脑子啦 o(╥﹏╥)o
求一个一劳永逸的方法......

[line]2[/line]

已知：稀疏无向连通图 G，有 n 个顶点， m 条边，每个顶点存有一个数值 i 代表该顶点的颜色。
保证：0 < c < 8; c <= n < 256; n <= m < 1024。
求：按照游戏规则完成所需要的最小染色次数k, 以及对应的任意可行方案（第 i 次操作将 v 号顶点染为颜色 t）。

Input:
  integer n, m;
  n.times {
integer c[n];
  };
  m.times {
integer pair (a, b);
  };

Output:
  integer k;
  k.times {
integer pair (v, t);
  };

Sample 1:

  Input:
6, 6;
1, 1, 1, 2, 2, 2;
1, 2; 2, 3; 3, 4; 4, 5; 5, 6; 6, 1;

  Output:
1;
1, 2;

Sample 2:

  Input:
5, 6;
1, 1, 2, 1, 2;
1, 2; 2, 3; 3, 4; 4, 5; 5, 1; 2, 5;

  Output:
2;
4, 2; 4, 1;

游戏截图

作者: defisym 时间: 2017-4-15 22:27
这满满的ACM既视感……
去搜题解啊（大雾

欢迎光临 Project1 (https://rpg.blue/)