HDU 4611 Balls Rearrangement
令lcm=LCM(a,b)，gcd=GCD(a,b)。cal(n,a,b)表示sum(abs(i%a-i%b))，0<=i<n。
显然，答案就是cal(lcm,a,b)*(n/lcm)+cal(n%lcm,a,b)。
cal(n,a,b)可以通过暴力得到，即对i%a和i%b的值分段，连续的一段（遇到0终止）可以直接得到值。
因此，每段的长度将直接影响到时间复杂度。
当lcm较小时，cal中的n不会很大，即使每段长度很小也无所谓。
当lcm较大时，每段的长度会比较大。
#include<iostream>
#include<algorithm>
typedef long long LL;
using namespace std;
LL GCD(LL x, LL y) {
return y ? GCD(y, x % y) : x;
}
LL LCM(LL x, LL y) {
return x / GCD(x, y) * y;
}
LL cal(LL n, LL a, LL b) {
LL ans = ;
LL x, y, tmp;
x = ;
y = a;
for (LL i = a; i < n;) {
tmp = min(a - x, b - y);
if (i + tmp > n) {
tmp = n - i;
}
i += tmp;
ans += tmp * abs(x - y);
x = (x + tmp) % a;
y = (y + tmp) % b;
}
return ans;
}
int main() {
int T;
LL n, a, b;
LL lcm;
LL ans;
cin >> T;
while (T--) {
cin >> n >> a >> b;
if (a == b) {
ans = ;
} else {
if (a > b) {
swap(a, b);
}
lcm = LCM(a, b);
ans = (n / lcm) * cal(lcm, a, b) + cal(n % lcm, a, b);
}
cout << ans << endl;
}
return ;
}
HDU 4612 Warm up
把桥处理出来，对双连通分量缩点，得到一棵树。
求树上最长链，将最长链的两端连起来，剩下的桥的个数就是答案。
#pragma comment(linker,"/STACK:102400000,102400000") #include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 200010
#define MAXM 2000010
using namespace std;
int first[MAXN], next[MAXM], v[MAXM], e;
int dfn[MAXN], low[MAXN];
int belong[MAXN];
bool vis[MAXN];
int n, m;
int dp[MAXN][];
int father[MAXN];
struct Edge {
int x, y;
};
Edge g[MAXM];
Edge tree[MAXM];
inline void addEdge(int x, int y) {
v[e] = y;
next[e] = first[x];
first[x] = e++;
}
void makeSet(int n) {
for (int i = ; i <= n; i++) {
father[i] = i;
}
}
int findSet(int x) {
if (father[x] != x) {
father[x] = findSet(father[x]);
}
return father[x];
}
void myUnion(int x, int y) {
x = findSet(x);
y = findSet(y);
if (x != y) {
father[x] = y;
}
}
void dfs(int x, int index, int depth) {
dfn[x] = low[x] = depth;
for (int i = first[x]; i != -; i = next[i]) {
if ((i ^ ) == index) {
continue;
}
int y = v[i];
if (dfn[y]) {
low[x] = min(low[x], dfn[y]);
} else {
dfs(y, i, depth + );
low[x] = min(low[x], low[y]);
if (low[y] > dfn[x]) {
tree[m].x = x;
tree[m++].y = y;
} else {
myUnion(x, y);
}
}
}
}
void search(int x) {
vis[x] = true;
for (int i = first[x]; i != -; i = next[i]) {
int y = v[i];
if (!vis[y]) {
search(y);
if (dp[y][] + >= dp[x][]) {
dp[x][] = dp[x][];
dp[x][] = dp[y][] + ;
} else if (dp[y][] + > dp[x][]) {
dp[x][] = dp[y][] + ;
}
}
}
}
int main() {
int i;
int ans;
int cnt;
while (scanf("%d%d", &n, &m), n) {
e = ;
memset(first, -, sizeof(first));
for (i = ; i < m; i++) {
scanf("%d%d", &g[i].x, &g[i].y);
addEdge(g[i].x, g[i].y);
addEdge(g[i].y, g[i].x);
}
makeSet(n);
m = ;
memset(dfn, , sizeof(dfn));
dfs(, -, );
memset(belong, -, sizeof(belong));
cnt = ;
for (i = ; i <= n; i++) {
if (belong[findSet(i)] == -) {
belong[findSet(i)] = ++cnt;
}
belong[i] = belong[findSet(i)];
}
e = ;
memset(first, -, sizeof(first));
for (i = ; i < m; i++) {
addEdge(belong[tree[i].x], belong[tree[i].y]);
addEdge(belong[tree[i].y], belong[tree[i].x]);
}
if (m == ) {
ans = ;
} else {
memset(dp, , sizeof(dp));
memset(vis, false, sizeof(vis));
search(belong[tree[].x]);
ans = ;
for (i = ; i <= cnt; i++) {
ans = max(ans, dp[i][] + dp[i][]);
}
ans = m - ans;
}
printf("%d\n", ans);
}
return ;
}
HDU 4614Vases and Flowers
K=1，二分得到起点和终点，区间覆盖为1。
K=2，区间求和，区间覆盖为0。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 50010
struct node {
int lazy;
int sum;
} tree[MAXN << ];
inline void pushUp(int rt) {
tree[rt].sum = tree[rt << ].sum + tree[rt << | ].sum;
}
void build(int L, int R, int rt) {
tree[rt].lazy = -;
tree[rt].sum = ;
if (L != R) {
int mid = (L + R) >> ;
build(L, mid, rt << );
build(mid + , R, rt << | );
}
}
inline void pushDown(int mid, int L, int R, int rt) {
if (tree[rt].lazy != -) {
tree[rt << ].lazy = tree[rt << | ].lazy = tree[rt].lazy;
tree[rt << ].sum = tree[rt].lazy * (mid - L + );
tree[rt << | ].sum = tree[rt].lazy * (R - mid);
tree[rt].lazy = -;
}
}
int sum(int x, int y, int L, int R, int rt) {
if (x <= L && R <= y) {
return tree[rt].sum;
} else {
int mid = (L + R) >> ;
pushDown(mid, L, R, rt);
int ans = ;
if (x <= mid) {
ans += sum(x, y, L, mid, rt << );
}
if (y > mid) {
ans += sum(x, y, mid + , R, rt << | );
}
pushUp(rt);
return ans;
}
}
void cover(int x, int y, int val, int L, int R, int rt) {
if (x <= L && R <= y) {
tree[rt].lazy = val;
tree[rt].sum = (R - L + ) * val;
} else {
int mid = (L + R) >> ;
pushDown(mid, L, R, rt);
if (x <= mid) {
cover(x, y, val, L, mid, rt << );
}
if (y > mid) {
cover(x, y, val, mid + , R, rt << | );
}
pushUp(rt);
}
}
int main() {
int T;
int n, m;
int k, a, b;
int x, y;
int low, high, mid;
int tot;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
build(, n - , );
while (m--) {
scanf("%d%d%d", &k, &a, &b);
if (k == ) {
tot = n - a - sum(a, n - , , n - , );
tot = min(tot, b);
if (tot == ) {
puts("Can not put any one.");
} else {
low = a;
high = n;
while (low < high) {
mid = (low + high) >> ;
if (mid - a + - sum(a, mid, , n - , ) >= ) {
high = mid;
x = mid;
} else {
low = mid + ;
}
}
low = a;
high = n;
while (low < high) {
mid = (low + high) >> ;
if (mid - a + - sum(a, mid, , n - , ) >= tot) {
high = mid;
y = mid;
} else {
low = mid + ;
}
}
printf("%d %d\n", x, y);
cover(x, y, , , n - , );
}
} else {
printf("%d\n", sum(a, b, , n - , ));
cover(a, b, , , n - , );
}
}
putchar('\n');
}
return ;
}
HDU 4616 Game
up[i][j][0]表示从下往上走，经历j个障碍的最大收益。
up[i][j][1]表示从下往上走，经历j个障碍的次大收益。
down[i][j][0]表示从上往下走，经历j个障碍的最大收益。
down[i][j][1]表示从上往下走，经历j个障碍的次大收益。
答案可能由up[i][j][0]+up[i][j][1]-val[i]，up[i][j][0]+down[i][j][0]-val[i]，up[i][j][1]+down[i][j][0]-val[i]，up[i][j][0]+down[i][j][1]-val[i]得到。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 100010
#define MAXM 4
#define oo 987654321
using namespace std;
bool vis[MAXN];
int first[MAXN], next[MAXN], v[MAXN], e;
int n, m;
int val[MAXN], trap[MAXN];
int up[MAXN][MAXM][], fromUp[MAXN][MAXM][];
int down[MAXN][MAXM][], fromDown[MAXN][MAXM][];
inline void addEdge(int x, int y) {
v[e] = y;
next[e] = first[x];
first[x] = e++;
}
void dfs(int x) {
vis[x] = true;
for (int i = ; i <= m; i++) {
for (int j = ; j < ; j++) {
up[x][i][j] = down[x][i][j] = -oo;
}
}
up[x][trap[x]][] = val[x];
if (trap[x]) {
down[x][trap[x]][] = val[x];
}
for (int i = first[x]; i != -; i = next[i]) {
int y = v[i];
if (!vis[y]) {
dfs(y);
for (int j = trap[x]; j <= m; j++) {
if (up[x][j][] <= up[y][j - trap[x]][] + val[x]) {
up[x][j][] = up[x][j][];
fromUp[x][j][] = fromUp[x][j][];
up[x][j][] = up[y][j - trap[x]][] + val[x];
fromUp[x][j][] = y;
} else if (up[x][j][] < up[y][j - trap[x]][] + val[x]) {
up[x][j][] = up[y][j - trap[x]][] + val[x];
fromUp[x][j][] = y;
}
if (down[x][j][] <= down[y][j - trap[x]][] + val[x]) {
down[x][j][] = down[x][j][];
fromDown[x][j][] = fromDown[x][j][];
down[x][j][] = down[y][j - trap[x]][] + val[x];
fromDown[x][j][] = y;
} else if (down[x][j][] < down[y][j - trap[x]][] + val[x]) {
down[x][j][] = down[y][j - trap[x]][] + val[x];
fromDown[x][j][] = y;
}
}
}
}
}
int main() {
int T;
int i, j, k;
int x, y;
int ans;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
for (i = ; i < n; i++) {
scanf("%d%d", &val[i], &trap[i]);
}
e = ;
memset(first, -, sizeof(first));
for (i = ; i < n; i++) {
scanf("%d%d", &x, &y);
addEdge(x, y);
addEdge(y, x);
}
memset(vis, false, sizeof(vis));
dfs();
ans = -oo;
for (i = ; i < n; i++) {
for (j = ; j <= m; j++) {
if (j < m) {
ans = max(ans, up[i][j][]);
}
for (k = ; k + j <= m; k++) {
if (fromUp[i][j][] != fromDown[i][k][]) {
ans = max(ans, up[i][j][] + down[i][k][] - val[i]);
} else {
ans = max(ans, up[i][j][] + down[i][k][] - val[i]);
ans = max(ans, up[i][j][] + down[i][k][] - val[i]);
}
if (k + j < m) {
ans = max(ans, up[i][j][] + up[i][k][] - val[i]);
}
}
}
}
printf("%d\n", ans);
}
return ;
}
HDU 4617 Weapon
对给定的平面求法向量，结合圆心，得到直线。
求空间直线的距离，若直线i与直线j的最短距离<=半径i+半径j，则相交；否则，答案就是任意两条直线距离的最小值。
#include<cstdio>
#include<cmath>
#include<algorithm>
#define eps 1e-8
#define oo 1e50
#define MAXN 55
using namespace std;
struct point3 {
double x, y, z;
};
struct line3 {
point3 a, b;
};
struct plane3 {
point3 a, b, c;
};
double r[MAXN];
double dis[MAXN][MAXN];
plane3 p[MAXN];
line3 l[MAXN];
double dist(point3 p1, point3 p2) {
return sqrt(
(p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y)
+ (p1.z - p2.z) * (p1.z - p2.z));
}
point3 xmult(point3 u, point3 v) {
point3 ret;
ret.x = u.y * v.z - v.y * u.z;
ret.y = u.z * v.x - u.x * v.z;
ret.z = u.x * v.y - u.y * v.x;
return ret;
}
point3 subt(point3 u, point3 v) {
point3 ret;
ret.x = u.x - v.x;
ret.y = u.y - v.y;
ret.z = u.z - v.z;
return ret;
}
point3 add(point3 u, point3 v) {
point3 ret;
ret.x = u.x + v.x;
ret.y = u.y + v.y;
ret.z = u.z + v.z;
return ret;
}
point3 pvec(plane3 s) {
return xmult(subt(s.a, s.b), subt(s.b, s.c));
}
double dmult(point3 u, point3 v) {
return u.x * v.x + u.y * v.y + u.z * v.z;
}
double vlen(point3 p) {
return sqrt(p.x * p.x + p.y * p.y + p.z * p.z);
}
double linetoline(line3 u, line3 v) {
point3 n = xmult(subt(u.a, u.b), subt(v.a, v.b));
return fabs(dmult(subt(u.a, v.a), n)) / vlen(n);
}
int dbcmp(double x, double y) {
if (fabs(x - y) < eps) {
return ;
} else {
return x > y ? : -;
}
}
int main() {
int T;
int n;
int i, j;
point3 tmp;
bool flag;
double ans;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
for (i = ; i < n; i++) {
scanf("%lf%lf%lf", &p[i].a.x, &p[i].a.y, &p[i].a.z);
scanf("%lf%lf%lf", &p[i].b.x, &p[i].b.y, &p[i].b.z);
scanf("%lf%lf%lf", &p[i].c.x, &p[i].c.y, &p[i].c.z);
r[i] = dist(p[i].a, p[i].b);
tmp = pvec(p[i]);
l[i].a = p[i].a;
l[i].b = add(l[i].a, tmp);
}
flag = false;
for (i = ; i < n; i++) {
dis[i][i] = ;
for (j = i + ; j < n; j++) {
dis[i][j] = dis[j][i] = linetoline(l[i], l[j]);
}
}
ans = oo;
for (i = ; i < n; i++) {
for (j = i + ; j < n; j++) {
if (dbcmp(dis[i][j], r[i] + r[j]) <= ) {
flag = true;
} else {
ans = min(ans, dis[i][j] - r[i] - r[j]);
}
}
}
if (flag) {
puts("Lucky");
} else {
printf("%.2lf\n", ans);
}
}
return ;
}
4618 Palindrome Sub-Array
回文串要分奇偶考虑。
分别枚举横，竖的数组，并枚举回文串的中间位置，二分哈希值求出最长回文串。
枚举横，竖数组的中间位置，二分答案。
复杂度O(n3log2n)，常数比较小。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 310
#define SEED 100000007
typedef unsigned long long LL;
using namespace std;
int n, m;
int ans;
int arr[MAXN][MAXN];
LL seed[MAXN];
LL hl[MAXN], hr[MAXN];
int r[MAXN][MAXN];
int c[MAXN][MAXN];
void init() {
seed[] = ;
for (int i = ; i < MAXN; i++) {
seed[i] = seed[i - ] * SEED;
}
}
void hash(int tmp[], int size) {
int i;
hl[] = tmp[];
for (i = ; i < size; i++) {
hl[i] = seed[i] * tmp[i] + hl[i - ];
}
hr[size - ] = tmp[size - ];
for (i = size - ; i >= ; i--) {
hr[i] = seed[size - i - ] * tmp[i] + hr[i + ];
}
}
bool isOK(int x0, int y0, int x1, int y1, int size) {
if (x0 <= y0 && x1 <= y1) {
LL a = hl[y0];
if (x0 - >= ) {
a -= hl[x0 - ];
}
LL b = hr[x1];
if (y1 + < size) {
b -= hr[y1 + ];
}
if (x0 > size - - y1) {
b *= seed[x0 - (size - - y1)];
} else {
a *= seed[size - - y1 - x0];
}
return a == b;
} else {
return false;
}
}
bool isOddGood(int x, int y, int len) {
int i;
for (i = x - ; i >= x - len; i--) {
if (r[i][y] < len) {
return false;
}
}
for (i = x + ; i <= x + len; i++) {
if (r[i][y] < len) {
return false;
}
}
for (i = y - ; i >= y - len; i--) {
if (c[x][i] < len) {
return false;
}
}
for (i = y + ; i <= y + len; i++) {
if (c[x][i] < len) {
return false;
}
}
return true;
}
void odd() {
int i, j;
int tmp[MAXN];
int low, high, mid, res;
memset(r, , sizeof(r));
for (i = ; i < n; i++) {
for (j = ; j < m; j++) {
tmp[j] = arr[i][j];
}
hash(tmp, m);
for (j = ; j < m - ; j++) {
res = ;
low = ;
high = min(j, m - - j) + ;
while (low < high) {
mid = (low + high) >> ;
if (isOK(j - mid, j - , j + , j + mid, m)) {
res = mid;
low = mid + ;
} else {
high = mid;
}
}
r[i][j] = res;
}
}
memset(c, , sizeof(c));
for (i = ; i < m; i++) {
for (j = ; j < n; j++) {
tmp[j] = arr[j][i];
}
hash(tmp, n);
for (j = ; j < n - ; j++) {
res = ;
low = ;
high = min(j, n - - j) + ;
while (low < high) {
mid = (low + high) >> ;
if (isOK(j - mid, j - , j + , j + mid, n)) {
res = mid;
low = mid + ;
} else {
high = mid;
}
}
c[j][i] = res;
}
}
for (i = ; i < n; i++) {
for (j = ; j < m; j++) {
if (r[i][j] && c[i][j]) {
res = ;
low = ;
high = min(r[i][j], c[i][j]) + ;
while (low < high) {
mid = (low + high) >> ;
if (isOddGood(i, j, mid)) {
low = mid + ;
res = mid;
} else {
high = mid;
}
}
ans = max(ans, res << | );
}
}
}
}
bool isEvenGood(int x, int y, int len) {
int i;
for (i = x - ; i > x - len; i--) {
if (r[i][y] < len) {
return false;
}
}
for (i = x + ; i <= x + len; i++) {
if (r[i][y] < len) {
return false;
}
}
for (i = y - ; i > y - len; i--) {
if (c[x][i] < len) {
return false;
}
}
for (i = y + ; i <= y + len; i++) {
if (c[x][i] < len) {
return false;
}
}
return true;
}
void even() {
int i, j;
int tmp[MAXN];
int low, high, mid, res;
memset(r, , sizeof(r));
for (i = ; i < n; i++) {
for (j = ; j < m; j++) {
tmp[j] = arr[i][j];
}
hash(tmp, m);
for (j = ; j < m - ; j++) {
res = ;
low = ;
high = min(j + , m - - j) + ;
while (low < high) {
mid = (low + high) >> ;
if (isOK(j - mid + , j, j + , j + mid, m)) {
res = mid;
low = mid + ;
} else {
high = mid;
}
}
r[i][j] = res;
}
}
memset(c, , sizeof(c));
for (i = ; i < m; i++) {
for (j = ; j < n; j++) {
tmp[j] = arr[j][i];
}
hash(tmp, n);
for (j = ; j < n - ; j++) {
res = ;
low = ;
high = min(j + , n - - j) + ;
while (low < high) {
mid = (low + high) >> ;
if (isOK(j - mid + , j, j + , j + mid, n)) {
res = mid;
low = mid + ;
} else {
high = mid;
}
}
c[j][i] = res;
}
}
for (i = ; i < n; i++) {
for (j = ; j < m; j++) {
if (r[i][j] && c[i][j]) {
res = ;
low = ;
high = min(r[i][j], c[i][j]) + ;
while (low < high) {
mid = (low + high) >> ;
if (isEvenGood(i, j, mid)) {
low = mid + ;
res = mid;
} else {
high = mid;
}
}
ans = max(ans, res << );
}
}
}
}
int main() {
int T;
int i, j;
init();
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
for (i = ; i < n; i++) {
for (j = ; j < m; j++) {
scanf("%d", &arr[i][j]);
}
}
ans = ;
odd();
even();
printf("%d\n", ans);
}
return ;
}
HDU 4619Warm up 2
有冲突的两个骨牌连边，求最大匹配。
最大独立集=顶点数-最大匹配。
#pragma comment(linker,"/STACK:102400000,102400000") #include<cstdio>
#include<cstring>
#include<vector>
#define MAXN 100010
#define MAXM 1000010
#define oo 123456789
using namespace std;
int first[MAXN], next[MAXM], v[MAXM], cost[MAXM], e;
int n, m;
int src, des;
inline void addEdge(int x, int y, int val) {
v[e] = y;
cost[e] = val;
next[e] = first[x];
first[x] = e++; v[e] = x;
cost[e] = ;
next[e] = first[y];
first[y] = e++;
}
int SAP() {
int pre[MAXN], cur[MAXN], dis[MAXN], gap[MAXN];
int flow = ;
int aug = oo;
int x, y;
bool flag;
for (int i = ; i < n; i++) {
cur[i] = first[i];
gap[i] = dis[i] = ;
}
gap[src] = n;
x = pre[src] = src;
while (dis[src] < n) {
flag = false;
for (int &j = cur[x]; j != -; j = next[j]) {
y = v[j];
if (cost[j] > && dis[x] == dis[y] + ) {
flag = true;
aug = min(aug, cost[j]);
pre[y] = x;
x = y;
if (x == des) {
flow += aug;
while (x != src) {
x = pre[x];
cost[cur[x]] -= aug;
cost[cur[x] ^ ] += aug;
}
aug = oo;
}
break;
}
}
if (flag) {
continue;
}
int tmp = n;
for (int j = first[x]; j != -; j = next[j]) {
y = v[j];
if (cost[j] > && dis[y] < tmp) {
tmp = dis[y];
cur[x] = j;
}
}
if ((--gap[dis[x]]) == ) {
break;
}
gap[dis[x] = tmp + ]++;
x = pre[x];
}
return flow;
}
struct Point {
int x, y;
};
struct Line {
Point a, b;
};
Line p[MAXN], q[MAXN];
bool equal(Point s, Point t) {
return s.x == t.x && s.y == t.y;
}
int main() {
int i, j;
int ans;
while (scanf("%d%d", &n, &m), n) {
e = ;
memset(first, -, sizeof(first));
src = n + m;
des = src + ;
for (i = ; i < n; i++) {
scanf("%d%d", &p[i].a.x, &p[i].a.y);
p[i].b = p[i].a;
p[i].b.x++;
addEdge(src, i, );
}
for (i = ; i < m; i++) {
scanf("%d%d", &q[i].a.x, &q[i].a.y);
q[i].b = q[i].a;
q[i].b.y++;
addEdge(n + i, des, );
}
for (i = ; i < n; i++) {
for (j = ; j < m; j++) {
if (equal(p[i].a, q[j].a) || equal(p[i].a, q[j].b)
|| equal(p[i].b, q[j].a) || equal(p[i].b, q[j].b)) {
addEdge(i, n + j, );
}
}
}
ans = n + m;
n = des + ;
ans -= SAP();
printf("%d\n", ans);
}
return ;
}
4620 Fruit Ninja Extreme
题目要求对于有奖励的切法，时间间隔不超过w，求有奖励切法的最大次数。
如果一个切法得不到奖励，那么应该选择不切。
考虑用搜索解决，没有剪枝的情况下，时间复杂度为230。
假设当前在cur，把cur之后的所有切法都假设是最优的，却无法更新答案，那么就没有必要再搜下去了。
这样可以把时间复杂度降低到可以接受的范围内。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 210
using namespace std;
int n, m, w;
bool vis[MAXN];
struct node {
int time;
int fruit[MAXN];
int cnt;
int pos;
friend bool operator<(node a, node b) {
return a.time < b.time;
}
} arr[MAXN];
int tmp[MAXN], tmpSize;
int ans[MAXN], ansSize;
void dfs(int cur, int pre, int left) {
if (tmpSize > ansSize) {
ansSize = tmpSize;
for (int i = ; i < tmpSize; i++) {
ans[i] = tmp[i];
}
}
if (left < ) {
return;
}
if (cur >= n) {
return;
}
if (n - cur + tmpSize <= ansSize) {
return;
}
int cut[MAXN], cutSize;
for (int i = cur; i < n; i++) {
if (pre != - && arr[i].time - arr[pre].time > w) {
break;
}
cutSize = ;
for (int j = ; j < arr[i].cnt; j++) {
if (!vis[arr[i].fruit[j]]) {
cut[cutSize++] = arr[i].fruit[j];
}
}
if (cutSize < ) {
continue;
}
for (int j = ; j < cutSize; j++) {
vis[cut[j]] = true;
}
tmp[tmpSize++] = arr[i].pos;
dfs(i + , i, left - cutSize);
tmpSize--;
for (int j = ; j < cutSize; j++) {
vis[cut[j]] = false;
}
}
}
int main() {
int T;
int i, j;
scanf("%d", &T);
while (T--) {
scanf("%d%d%d", &n, &m, &w);
for (i = ; i < n; i++) {
scanf("%d%d", &arr[i].cnt, &arr[i].time);
for (j = ; j < arr[i].cnt; j++) {
scanf("%d", &arr[i].fruit[j]);
}
arr[i].pos = i + ;
}
sort(arr, arr + n);
memset(vis, false, sizeof(vis));
tmpSize = ;
ansSize = ;
dfs(, -, m);
printf("%d\n", ansSize);
sort(ans, ans + ansSize);
for (i = ; i < ansSize; i++) {
printf("%d", ans[i]);
if (i < ansSize - ) {
putchar(' ');
} else {
putchar('\n');
}
}
}
return ;
}