T1

最小生成树，不讲了。

T2

暴力模拟。

T3

分组背包，太简单，不讲了。

```cpp

#include<bits/stdc++.h>

#define int long long

using namespace std;

int read(){

    int sum = 0, f = 1;

    char ch = getchar();

    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -f;

    for(; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch ^ 48);

    return sum * f; 

}

void write(int x){

    if(x < 0) putchar('-'), x = -x;

    if(x > 9) write(x / 10);

    putchar('0' + x % 10);

    return;

}

const int N = 2e3 + 10;

int n, T, dp[N][N];

struct node{

int t, v;

node(int t = 0, int v = 0) : t(t), v(v) {}

};

vector<node> g[N];

signed main(){

    n = read(), T = read();

    for(int i = 1; i <= n; ++ i){

    int m = read();

    for(int j = 1; j <= m; ++ j){

    int t = read(), v = read();

    g[i].push_back(node(t, v));

}

for(int j = 1; j < m; ++ j){

g[i][j].t += g[i][j - 1].t;

g[i][j].v += g[i][j - 1].v;

}

}

for(int i = 1; i <= n; ++ i){

for(int j = 1; j <= T; ++ j){

dp[i][j] = dp[i - 1][j];

for(int k = 0; k < g[i].size(); ++ k)

if(j >= g[i][k].t)

dp[i][j] = max(dp[i][j], dp[i - 1][j - g[i][k].t] + g[i][k].v);

}

}

write(dp[n][T]);

    return 0;

}

```

T4