#P18725. Graph Stabilization

    ID: 18061 传统题 2000ms 1024MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-多源 BFS二分图建模带权二分图匹配KM 算法

Graph Stabilization

Graph Stabilization

给定一张有 n 个顶点的无向图,顶点 i 上写着整数 a_i。两个顶点之间有边相连时,称它们互为邻居。

如果顶点 i 至少有一个邻居 j 满足下列条件之一,就称 i 稳定:

  • a_j < a_i;
  • a_j ⊕ a_i = k,其中 ⊕ 是按位异或。

否则,i 不稳定。图的稳定化过程如下:如果不存在不稳定顶点,过程结束;否则,删除编号最小的不稳定顶点及其所有关联边,然后重复。图的稳定度是过程结束后剩余的顶点数量。

现在给定 a、k 和每条边的费用。你可以预先删除任意一些边(也可以不删或全删)。需要依次优化两个目标:先使删除后的图的稳定度尽可能大;在满足这一点的方案中,再使预先删除的边的费用之和尽可能大。

输入格式

第一行三个整数 n,m,k:1≤n≤100,0≤m≤n(n−1)/2,1≤k≤127。

第二行 n 个整数 a_1,…,a_n,满足 0≤a_i≤127。

接下来 m 行,第 i 行包含 x_i,y_i,c_i,表示原编号为 i 的边。1≤x_i,y_i≤n,x_i≠y_i,1≤c_i≤10^9。任意一对顶点之间至多有一条边。

输出格式

输出一个整数 e(0≤e≤m),表示预先删除的边数。然后输出 e 个互不相同的整数,取值为 1 到 m,表示这些边在原输入中的编号。编号可以按任意顺序输出。如有多个最优答案,输出任意一个。e=0 时无需输出编号。

原样例 1

5 6 1
0 1 2 2 2
1 2 1
1 3 2
2 3 3
3 4 4
3 5 5
4 5 6
4
3 4 5 6

原样例 2

8 10 3
34 5 6 33 4 7 1 4
1 3 11
4 1 15
8 6 10
5 7 1
5 6 10
5 2 5
2 6 2
3 2 4
5 3 1
4 2 2
5
2 4 6 7 9