#P18725. Graph Stabilization
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